Mac Lane s planarity criterion

In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces. It states that a finite graph G is planar if and only if the cycle space C(G), which in topologists' terms is the space of 1-cycles with mod 2 coefficients of G as simplicial complex, has a 2-basis, i.e. a vector space basis over the field with two elements, such that a given edge appears in at most two basis vectors. The only if direction is intuitively clear. This result is due to Saunders Mac Lane (1937).

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.