Bundled crossings in embedded graphs

M. Fink; J. Hershberger; S. Suri; K.A.B. Verbeek

doi:10.1007/978-3-662-49529-2_34

Bundled crossings in embedded graphs

M. Fink, J. Hershberger, S. Suri, K.A.B. Verbeek

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

10 Citations (Scopus)

3 Downloads (Pure)

Abstract

Edge crossings in a graph drawing are an important factor in the drawing’s quality. However, it is not just the presence of crossings that determines the drawing’s quality: any drawing of a nonplanar graph in the plane necessarily contains crossings, but the geometric structure of those crossings can have a significant impact on the drawing’s readability. In particular, the structure of two disjoint groups of locally parallel edges (bundles) intersecting in a complete crossbar (a bundled crossing) is visually simpler—even if it involves many individual crossings—than an equal number of random crossings scattered in the plane. In this paper, we investigate the complexity of partitioning the crossings of a given drawing of a graph into a minimum number of bundled crossings. We show that this problem is NP-hard, propose a constant-factor approximation scheme for the case of circular embeddings, where all vertices lie on the outer face, and show that the bundled crossings problem in general graphs is related to a minimum dissection problem.

Original language	English
Title of host publication	LATIN 2016: Theoretical Informatics
Subtitle of host publication	12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings
Editors	E. Kranakis, G. Navarro, E. Chavez
Place of Publication	Dordrecht
Publisher	Springer
Pages	454-468
Number of pages	15
ISBN (Electronic)	978-3-662-49529-2
ISBN (Print)	978-3-662-49528-5
DOIs	https://doi.org/10.1007/978-3-662-49529-2_34
Publication status	Published - 2016
Event	12th Latin American Theoretical INformatics Symposium (LATIN 2016) - Ensenada, Mexico Duration: 11 Apr 2016 → 15 Apr 2016 Conference number: 12

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9644
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	12th Latin American Theoretical INformatics Symposium (LATIN 2016)
Abbreviated title	LATIN 2016
Country/Territory	Mexico
City	Ensenada
Period	11/04/16 → 15/04/16

Access to Document

10.1007/978-3-662-49529-2_34

Cite this

Fink, M., Hershberger, J., Suri, S., & Verbeek, K. A. B. (2016). Bundled crossings in embedded graphs. In E. Kranakis, G. Navarro, & E. Chavez (Eds.), LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings (pp. 454-468). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9644). Springer. https://doi.org/10.1007/978-3-662-49529-2_34

Fink, M. ; Hershberger, J. ; Suri, S. et al. / Bundled crossings in embedded graphs. LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings. editor / E. Kranakis ; G. Navarro ; E. Chavez. Dordrecht : Springer, 2016. pp. 454-468 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9f5a52419bbc457db1535b98a74915bc,

title = "Bundled crossings in embedded graphs",

abstract = "Edge crossings in a graph drawing are an important factor in the drawing{\textquoteright}s quality. However, it is not just the presence of crossings that determines the drawing{\textquoteright}s quality: any drawing of a nonplanar graph in the plane necessarily contains crossings, but the geometric structure of those crossings can have a significant impact on the drawing{\textquoteright}s readability. In particular, the structure of two disjoint groups of locally parallel edges (bundles) intersecting in a complete crossbar (a bundled crossing) is visually simpler—even if it involves many individual crossings—than an equal number of random crossings scattered in the plane. In this paper, we investigate the complexity of partitioning the crossings of a given drawing of a graph into a minimum number of bundled crossings. We show that this problem is NP-hard, propose a constant-factor approximation scheme for the case of circular embeddings, where all vertices lie on the outer face, and show that the bundled crossings problem in general graphs is related to a minimum dissection problem.",

author = "M. Fink and J. Hershberger and S. Suri and K.A.B. Verbeek",

year = "2016",

doi = "10.1007/978-3-662-49529-2_34",

language = "English",

isbn = "978-3-662-49528-5",

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

publisher = "Springer",

pages = "454--468",

editor = "E. Kranakis and G. Navarro and E. Chavez",

booktitle = "LATIN 2016: Theoretical Informatics",

address = "Germany",

note = "12th Latin American Theoretical INformatics Symposium (LATIN 2016), LATIN 2016 ; Conference date: 11-04-2016 Through 15-04-2016",

}

Fink, M, Hershberger, J, Suri, S & Verbeek, KAB 2016, Bundled crossings in embedded graphs. in E Kranakis, G Navarro & E Chavez (eds), LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9644, Springer, Dordrecht, pp. 454-468, 12th Latin American Theoretical INformatics Symposium (LATIN 2016), Ensenada, Mexico, 11/04/16. https://doi.org/10.1007/978-3-662-49529-2_34

Bundled crossings in embedded graphs. / Fink, M.; Hershberger, J.; Suri, S. et al.
LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings. ed. / E. Kranakis; G. Navarro; E. Chavez. Dordrecht: Springer, 2016. p. 454-468 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9644).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Bundled crossings in embedded graphs

AU - Fink, M.

AU - Hershberger, J.

AU - Suri, S.

AU - Verbeek, K.A.B.

N1 - Conference code: 12

PY - 2016

Y1 - 2016

N2 - Edge crossings in a graph drawing are an important factor in the drawing’s quality. However, it is not just the presence of crossings that determines the drawing’s quality: any drawing of a nonplanar graph in the plane necessarily contains crossings, but the geometric structure of those crossings can have a significant impact on the drawing’s readability. In particular, the structure of two disjoint groups of locally parallel edges (bundles) intersecting in a complete crossbar (a bundled crossing) is visually simpler—even if it involves many individual crossings—than an equal number of random crossings scattered in the plane. In this paper, we investigate the complexity of partitioning the crossings of a given drawing of a graph into a minimum number of bundled crossings. We show that this problem is NP-hard, propose a constant-factor approximation scheme for the case of circular embeddings, where all vertices lie on the outer face, and show that the bundled crossings problem in general graphs is related to a minimum dissection problem.

AB - Edge crossings in a graph drawing are an important factor in the drawing’s quality. However, it is not just the presence of crossings that determines the drawing’s quality: any drawing of a nonplanar graph in the plane necessarily contains crossings, but the geometric structure of those crossings can have a significant impact on the drawing’s readability. In particular, the structure of two disjoint groups of locally parallel edges (bundles) intersecting in a complete crossbar (a bundled crossing) is visually simpler—even if it involves many individual crossings—than an equal number of random crossings scattered in the plane. In this paper, we investigate the complexity of partitioning the crossings of a given drawing of a graph into a minimum number of bundled crossings. We show that this problem is NP-hard, propose a constant-factor approximation scheme for the case of circular embeddings, where all vertices lie on the outer face, and show that the bundled crossings problem in general graphs is related to a minimum dissection problem.

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

U2 - 10.1007/978-3-662-49529-2_34

DO - 10.1007/978-3-662-49529-2_34

M3 - Conference contribution

AN - SCOPUS:84961705001

SN - 978-3-662-49528-5

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

SP - 454

EP - 468

BT - LATIN 2016: Theoretical Informatics

A2 - Kranakis, E.

A2 - Navarro, G.

A2 - Chavez, E.

PB - Springer

CY - Dordrecht

T2 - 12th Latin American Theoretical INformatics Symposium (LATIN 2016)

Y2 - 11 April 2016 through 15 April 2016

ER -

Fink M, Hershberger J, Suri S, Verbeek KAB. Bundled crossings in embedded graphs. In Kranakis E, Navarro G, Chavez E, editors, LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings. Dordrecht: Springer. 2016. p. 454-468. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-49529-2_34

Bundled crossings in embedded graphs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this