In mathematics, Whitney's planarity criterion is a

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

-theoretic characterization of

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s, named after

Hassler Whitney Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration t ...

. It states that a graph ''G'' is planar if and only if its

graphic matroid In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co- ...

is also cographic (that is, it is the

dual matroid In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it... Matroid duals go back to the original paper by Hassler Wh ...

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 In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...

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 In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...

) ''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 the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...

in ''G'' corresponds to the

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...

of a spanning tree in ''H'', and vice versa.. 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. 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.

References

{{reflist Matroid theory Planar graphs