Abstract
We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that constructs such a drawing, if it exists. We also show that some almost-planar graphs require exponential area for a straight-line drawing.
Original language | English |
---|---|
Title of host publication | Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings |
Editors | Frank Dehne, Jorg-Rudiger Sack, Ulrike Stege |
Publisher | Springer Verlag |
Pages | 301-313 |
Number of pages | 13 |
ISBN (Print) | 9783319218397 |
DOIs | |
Publication status | Published - 2015 |
Externally published | Yes |
Event | 14th International Symposium on Algorithms and Data Structures, WADS 2015 - Victoria, Canada Duration: 5 Aug 2015 → 7 Aug 2015 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 9214 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 14th International Symposium on Algorithms and Data Structures, WADS 2015 |
---|---|
Country/Territory | Canada |
City | Victoria |
Period | 5/08/15 → 7/08/15 |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science