Planarity Testing - Planarity Criteria

Planarity Criteria

Planarity testing algorithms typically take advantage of theorems in graph theory that characterize the set of planar graphs in terms that are independent of graph drawings. These include

• Kuratowski's theorem that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K₅ (the complete graph on five vertices) or K_3,3 (the utility graph, a complete bipartite graph on six vertices, three of which connect to each of the other three).
• Wagner's theorem that a graph is planar if and only if it does not contain a minor (subgraph of a contraction) that is isomorphic to K₅ or K_3,3.
• The Fraysseix–Rosenstiehl planarity criterion, characterizing planar graphs in terms of a left-right ordering of the edges in a depth-first search tree.

The Fraysseix–Rosenstiehl planarity criterion can be used directly as part of algorithms for planarity testing, while Kuratowski's and Wagner's theorems have indirect applications: if an algorithm can find a copy of K₅ or K_3,3 within a given graph, it can be sure that the input graph is not planar and return without additional computation.

Other planarity criteria, that characterize planar graphs mathematically but are less central to planarity testing algorithms, include Whitney's planarity criterion that a graph is planar if and only if its graphic matroid is also cographic, MacLane's planarity criterion characterizing planar graphs by the bases of their cycle spaces, Schnyder's theorem characterizing planar graphs by the order dimension of an associated partial order, and Colin de Verdière's planarity criterion using spectral graph theory.