@inproceedings{cf8227743e87466c8177800ef3eb494e,
title = "Straight-line drawability of a planar graph plus an edge",
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.",
author = "Peter Eades and Hong, \{Seok Hee\} and Giuseppe Liotta and Naoki Katoh and Poon, \{Sheung Hung\}",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 14th International Symposium on Algorithms and Data Structures, WADS 2015 ; Conference date: 05-08-2015 Through 07-08-2015",
year = "2015",
doi = "10.1007/978-3-319-21840-3\_25",
language = "English",
isbn = "9783319218397",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "301--313",
editor = "Frank Dehne and Jorg-Rudiger Sack and Ulrike Stege",
booktitle = "Algorithms and Data Structures - 14th International Symposium, WADS 2015, Proceedings",
address = "Germany",
}