Testing Full Outer-2-planarity

S. Hong and H. Nagamochi, "Beyond Planarity: Testing Full Outer-2-Planarity in Linear Time", TR [2014-003], Department of Applied Mathematics and Physics, Graduate School of Informatics, University of Kyoto, Japan, 2014

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.