A linear-time algorithm for testing full outer-2-planarity

A planar graph can be drawn without edge crossings in the plane. It is well known that testing planarity of a graph can be solved in linear time. A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one crossing. Testing 1-planarity of a graph is known to be NP-complete. This paper initiates the problem of testing 2-planarity of a graph, in particular, testing “full-outer-2-planarity” of a graph. A graph is outer- k-planar for an integer k≥0, if it admits an outer-k-planar embedding, that is, every vertex is on the outer boundary and no edge has more than k crossings. A graph is full-outer-k-planar, if it admits a full-outer-k-planar embedding, that is, an outer-k-planar embedding such that no crossing appears along the outer boundary. We present several structural properties of triconnected outer-2-planar graphs and full-outer-2-planar graphs, and prove that every triconnected full-outer-2-planar graph has a constant number of full-outer-2-planar embeddings. Based on these properties, we present linear-time algorithms for testing full-outer-2-planarity of a graph G, where G is connected, biconnected or triconnected. The algorithm also produces a full-outer-2-planar embedding of a graph, if it exists. Moreover, we show that every outer-k-planar embedding admits a straight-line drawing.