S. Hong and H. Nagamochi, "Beyond Planarity: Testing Full Outer2Planarity in Linear Time", TR [2014003], Department of Applied Mathematics and Physics, Graduate School of Informatics, University of Kyoto, Japan, 2014
A graph is 1planar, if it admits a 1planar embedding, where each edge has at most one
crossing. Unfortunately, testing 1planarity of a graph is known as NPcomplete.
This paper considers the problem of testing 2planarity of a graph, in particular,testing full outer2
planarity of a graph. A graph is fullyouter2planar, if it admits a fullyouter2planar 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 outer2
planar graphs and fullyouter2planar graphs, and prove that triconnected fullyouter2planar graphs
have constant number of fullyouter2planar embeddings. Based on these properties, we present
a lineartime algorithm for testing fully outer2planarity of a graph G, where G is triconnected,
biconnected and oneconnected. The algorithm also produce a fully outer2planar embedding of a
graph, if it exists. We also show that every fullyouter2planar embedding admits a straightline
drawing.
