Outer Planarity

Definition

A graph is outerplanar if it can be embedded in the plane such that no two edges cross and all vertices are incident to the same face, which we chose to be the outer one.

Complexity

Chartrand and Harary (1967), who initially studied the problem, provide a Kuratowsky-style characterisation as graphs that do not contain a subdivision of \(K_4\) or \(K_{2,3}\). Outer Planarity can be tested in linear time (Mitchell 1979). A linear-time algorithm also follows from the reduction to the linear-time solvable (Standard) Planarity problem.

Related Problems

The problem can be reduced to (Standard) Planarity by inserting an apex vertex that is connected to all other vertices (Schaefer 2013).

See also

• Wikipedia Article
• Information System on Graph Classes and their Inclusions Entry

References

Chartrand, Gary, and Frank Harary. 1967. “Planar Permutation Graphs.” Ann. Inst. H. Poincaré Sect. B (N.S.) 3: 433–38.

Mitchell, Sandra L. 1979. “Linear Algorithms to Recognize Outerplanar and Maximal Outerplanar Graphs.” Information Processing Letters 9 (5): 229–32. https://doi.org/10.1016/0020-0190(79)90075-9.

Schaefer, Marcus. 2013. “Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants.” Journal of Graph Algorithms and Applications 17 (4): 367–440. https://doi.org/10.7155/jgaa.00298.