Colored Point-Set Embeddings of Acyclic Graphs

Di Giacomo, Emilio and Gasieniec, Leszek and Liotta, Giuseppe and Navarra, Alfredo (2017) Colored Point-Set Embeddings of Acyclic Graphs. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 413-425(Official URL:

Full text not available from this repository.


We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require Ω(n23) edges each having Ω(n13) bends in the worst case. The lower bound holds even when the function that maps vertices to points is not a bijection but it is defined by a 3-coloring. In contrast, a constant number of bends per edge can be obtained for 3-colored paths and for 3-colored caterpillars whose leaves all have the same color. Such results answer to a long standing open problem. The work has been supported in part by the European project “Geospatial based Environment for Optimisation Systems Addressing Fire Emergencies” (GEO-SAFE), contract no. H2020-691161, by the Network Sciences and Technologies (NeST) initiative at University of Liverpool, and by the Italian project: “RISE: un nuovo framework distribuito per data collection, monitoraggio e comunicazioni in contesti di emergency response”, Fondazione Cassa Risparmio Perugia, code 2016.0104.021.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.560 Geometry

Actions (login required)

View Item View Item