@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",

}