2015/04/24 by Peter Eades, Seok-Hee Hong, Eades, Peter +7
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1504.06540
arxiv created 2015/06/30 · arxiv updated 2015/07/01
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.