PlanarityTests

PlanarityTests concerns the problem of deciding whether a given undirected graph can be drawn on the plane without any edge crossings, and, in the positive case, producing a planar embedding of the graph. A planar embedding records how the edges are arranged around each vertex, effectively specifying the faces of the drawing.

Theoretical basis for planarity rests on Kuratowski’s theorem, which states that a graph is planar if and only if it contains no subdivision of K5 or K3,3. This characterization underpins many planarity algorithms and helps explain non-planarity certificates. Planarity can also be characterized by graph minors, and several practical criteria exist for fast checks on small or sparse graphs.

Algorithmically, planarity testing has a long history and several linear-time solutions. Early linear-time algorithms were developed by Hopcroft and Tarjan in the 1970s, with later refinements and alternatives such as Booth and Lueker’s PQ-tree approach and the more recent Boyer–Myrvold algorithm. Modern implementations typically run in O(n) time and O(n) space for a graph with n vertices and m edges, and can optionally output a planar embedding when the graph is planar.

Outputs of planarity tests include either a confirmation of planarity accompanied by an embedding (rotation system around vertices) or a non-planarity certificate (often a subdivision of K5 or K3,3). Planarity testing is fundamental in graph drawing, VLSI layout, and network visualization, and is supported by several graph libraries and toolkits.