Whitney's planarity criterion
In mathematics, Whitney's planarity criterion is a matroid-theoretic characterization of planar graphs, named after Hassler Whitney. It states that a graph G is planar if and only if its graphic matroid is also cographic.
In purely graph-theoretic terms, this criterion can be stated as follows: There must be another graph ' = and a bijective correspondence between the edges ' and the edges E of the original graph G, such that a subset T of E forms a spanning tree of G if and only if the edges corresponding to the complementary subset E − T form a spanning tree of .
Algebraic duals
An equivalent form of Whitney's criterion is that a graph G is planar if and only if it has a dual graph whose graphic matroid is dual to the graphic matroid of G.A graph whose graphic matroid is dual to the graphic matroid of G is known as an algebraic dual of G. Thus, Whitney's planarity criterion can be expressed succinctly as: a graph is planar if and only if it has an algebraic dual.
Topological duals
If a graph is embedded into a topological surface such as the plane, in such a way that every face of the embedding is a topological disk, then the dual graph of the embedding is defined as the graph H that has a vertex for every face of the embedding, and an edge for every adjacency between a pair of faces.According to Whitney's criterion, the following conditions are equivalent:
- The surface on which the embedding exists is topologically equivalent to the plane, sphere, or punctured plane
- H is an algebraic dual of G
- Every simple cycle in G corresponds to a minimal cut in H, and vice versa
- Every simple cycle in H corresponds to a minimal cut in G, and vice versa
- Every spanning tree in G corresponds to the complement of a spanning tree in H, and vice versa.