Testing Maximal 1-Planarity

P. Eades, S. Hong, N. Katoh, G. Liotta, P. Schweitzer and Y. Suzuki, "A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system", Theoretical Computer Science 513 (2013): 65-76.

A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete.

In this paper, we consider maximal 1-planar graphs. A graph G is maximal 1-planar if addition of any edge destroys 1-planarity of G. We first study combinatorial properties of maximal 1-planar embeddings. In particular, we show that in a maximal 1-planar embedding, the graph induced by the non-crossing edges is spanning and biconnected.

Using the properties, we show that the problem of testing maximal 1-planarity of a graph G can be solved in linear time, if a rotation system (i.e., the circular ordering of edges for each vertex) is given. We also prove that there is at most one maximal 1-planar embedding of G that is consistent with the given rotation system. Our algorithm also produces such an embedding in linear time, if it exists.