A planar graph and its dual. Every cycle in the blue graph is a minimal cut in the red graph, and vice versa, so the two graphs are algebraic duals and have dual graphic matroids.
In mathematics, Whitney's planarity criterion is a matroid-theoretic characterization of planar graphs, named after Hassler Whitney.[1] It states that a graph G is planar if and only if its graphic matroid is also cographic (that is, it is the dual matroid of another graphic matroid).
In purely graph-theoretic terms, this criterion can be stated as follows: There must be another (dual) graph G′=(V′,E′) and a bijective correspondence between the edges E′ 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 G′.
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 (or in some cases multigraph) 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
It is possible to define dual graphs of graphs embedded on nonplanar surfaces such as the torus, but these duals do not generally have the correspondence between cuts, cycles, and spanning trees required by Whitney's criterion.
↑ Tutte, W. T. (1965), "Lectures on matroids", Journal of Research of the National Bureau of Standards, 69B: 1–47, doi:10.6028/jres.069b.001, MR0179781 . See in particular section 2.5, "Bon-matroid of a graph", pp. 5–6, section 5.6, "Graphic and co-graphic matroids", pp. 19–20, and section 9, "Graphic matroids", pp. 38–47.
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
