%0 Journal Article
%T Straight-line Drawability of a Planar Graph Plus an Edge
%A Peter Eades
%A Seok-Hee Hong
%A Giuseppe Liotta
%A Naoki Katoh
%A Sheung-Hung Poon
%J Computer Science
%D 2015
%I arXiv
%X 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.
%U http://arxiv.org/abs/1504.06540v2