Bundled crossings in embedded graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)
2 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 languageEnglish
Title of host publicationLATIN 2016: Theoretical Informatics
Subtitle of host publication12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings
EditorsE. Kranakis, G. Navarro, E. Chavez
Place of PublicationDordrecht
PublisherSpringer
Pages454-468
Number of pages15
ISBN (Electronic)978-3-662-49529-2
ISBN (Print)978-3-662-49528-5
DOIs
Publication statusPublished - 2016
Event12th Latin American Theoretical INformatics Symposium (LATIN 2016) - Ensenada, Mexico
Duration: 11 Apr 201615 Apr 2016
Conference number: 12

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9644
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference12th Latin American Theoretical INformatics Symposium (LATIN 2016)
Abbreviated titleLATIN 2016
CountryMexico
CityEnsenada
Period11/04/1615/04/16

Fingerprint Dive into the research topics of 'Bundled crossings in embedded graphs'. Together they form a unique fingerprint.

  • 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). Dordrecht: Springer. https://doi.org/10.1007/978-3-662-49529-2_34