In mathematics, Whitney's planarity criterion is a

matroid In combinatorics, 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 Axiomatic system, axiomatically, the most significant being in terms ...

-theoretic characterization of

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

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, immersion (mathematics), immersions, characteristic classes and, ...

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

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

is also cographic (that is, it is the

dual matroid Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual number, a ...

of another graphic matroid). In purely graph-theoretic terms, this criterion can be stated as follows: There must be another (dual) 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 In the mathematics, mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each p ...

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 mor ...

) ''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 no ...

in ''G'' corresponds to the complement 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

{{Authority control Matroid theory Statements about planar graphs