Mac Lane's planarity criterion

From Wikipedia, the free encyclopedia

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

[edit] References

• S. Mac Lane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937), 22–32.