Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2014-003 (September 8, 2014)

Beyond Planarity: Testing Full Outer-2-Planarity in Linear Time
by Seok-Hee Hong and Hiroshi Nagamochi

pdf File

A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one crossing. Unfortunately, testing 1-planarity of a graph is known as NP-complete. This paper considers the problem of testing 2- planarity of a graph, in particular,testing full outer-2-planarity of a graph. A graph is fully-outer-2-planar, if it admits a fully-outer-2- planar embedding such that every vertex is on the outer boundary, no edge has more than two crossings, and no crossing appears along the outer boundary. We present several structural properties of triconnected outer-2-planar graphs and fully-outer-2-planar graphs, and prove that triconnected fully-outer-2-planar graphs have constant number of fully- outer-2-planar embeddings. Based on these properties, we present a linear-time algorithm for testing fully outer-2-planarity of a graph G, where G is triconnected, biconnected and oneconnected. The algorithm also produce a fully outer-2-planar embedding of a graph, if it exists. We also show that every fully-outer-2-planar embedding admits a straight -line drawing.