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