Colored point-set embeddings of acyclic graphs

Emilio Di Giacomo; Leszek Gasieniec; Giuseppe Liotta; Alfredo Navarra

doi:10.1007/978-3-319-73915-1_32

Colored point-set embeddings of acyclic graphs

Emilio Di Giacomo, Leszek Gasieniec, Giuseppe Liotta, Alfredo Navarra

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require Ω(n^2/3) edges each having Ω (n^1/3) 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.

Original language	English (US)
Title of host publication	Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers
Editors	Kwan-Liu Ma, Fabrizio Frati
Publisher	Springer Verlag
Pages	413-425
Number of pages	13
ISBN (Print)	9783319739144
DOIs	https://doi.org/10.1007/978-3-319-73915-1_32
State	Published - 2018
Externally published	Yes
Event	25th International Symposium on Graph Drawing and Network Visualization, GD 2017 - Boston, United States Duration: Sep 25 2017 → Sep 27 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10692 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th International Symposium on Graph Drawing and Network Visualization, GD 2017
Country/Territory	United States
City	Boston
Period	9/25/17 → 9/27/17

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-73915-1_32

Cite this

Di Giacomo, E., Gasieniec, L., Liotta, G., & Navarra, A. (2018). Colored point-set embeddings of acyclic graphs. In K.-L. Ma, & F. Frati (Eds.), Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers (pp. 413-425). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10692 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-73915-1_32

Colored point-set embeddings of acyclic graphs. / Di Giacomo, Emilio; Gasieniec, Leszek; Liotta, Giuseppe et al.
Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. ed. / Kwan-Liu Ma; Fabrizio Frati. Springer Verlag, 2018. p. 413-425 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10692 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Di Giacomo, E, Gasieniec, L, Liotta, G & Navarra, A 2018, Colored point-set embeddings of acyclic graphs. in K-L Ma & F Frati (eds), Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10692 LNCS, Springer Verlag, pp. 413-425, 25th International Symposium on Graph Drawing and Network Visualization, GD 2017, Boston, United States, 9/25/17. https://doi.org/10.1007/978-3-319-73915-1_32

Di Giacomo E, Gasieniec L, Liotta G, Navarra A. Colored point-set embeddings of acyclic graphs. In Ma KL, Frati F, editors, Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. Springer Verlag. 2018. p. 413-425. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-73915-1_32

Di Giacomo, Emilio ; Gasieniec, Leszek ; Liotta, Giuseppe et al. / Colored point-set embeddings of acyclic graphs. Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers. editor / Kwan-Liu Ma ; Fabrizio Frati. Springer Verlag, 2018. pp. 413-425 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{92d4c1deb36849ea85686ead1e5dd4f3,

title = "Colored point-set embeddings of acyclic graphs",

abstract = "We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require Ω(n2/3) edges each having Ω (n1/3) 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.",

author = "{Di Giacomo}, Emilio and Leszek Gasieniec and Giuseppe Liotta and Alfredo Navarra",

note = "Funding Information: 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 frame-work distribuito per data collection, monitoraggio e comunicazioni in contesti di emergency response”, Fondazione Cassa Risparmio Perugia, code 2016.0104.021. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2018.; 25th International Symposium on Graph Drawing and Network Visualization, GD 2017 ; Conference date: 25-09-2017 Through 27-09-2017",

year = "2018",

doi = "10.1007/978-3-319-73915-1_32",

language = "English (US)",

isbn = "9783319739144",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "413--425",

editor = "Kwan-Liu Ma and Fabrizio Frati",

booktitle = "Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers",

}

TY - GEN

T1 - Colored point-set embeddings of acyclic graphs

AU - Di Giacomo, Emilio

AU - Gasieniec, Leszek

AU - Liotta, Giuseppe

AU - Navarra, Alfredo

N1 - Funding Information: 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 frame-work distribuito per data collection, monitoraggio e comunicazioni in contesti di emergency response”, Fondazione Cassa Risparmio Perugia, code 2016.0104.021. Publisher Copyright: © Springer International Publishing AG 2018.

PY - 2018

Y1 - 2018

N2 - We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require Ω(n2/3) edges each having Ω (n1/3) 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.

AB - We show that any planar drawing of a forest of three stars whose vertices are constrained to be at fixed vertex locations may require Ω(n2/3) edges each having Ω (n1/3) 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.

UR - http://www.scopus.com/inward/record.url?scp=85041852223&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041852223&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-73915-1_32

DO - 10.1007/978-3-319-73915-1_32

M3 - Conference contribution

AN - SCOPUS:85041852223

SN - 9783319739144

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 413

EP - 425

BT - Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers

A2 - Ma, Kwan-Liu

A2 - Frati, Fabrizio

PB - Springer Verlag

T2 - 25th International Symposium on Graph Drawing and Network Visualization, GD 2017

Y2 - 25 September 2017 through 27 September 2017

ER -

Colored point-set embeddings of acyclic graphs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this