Mac Lane's planarity criterion
From Wikipedia, the free encyclopedia
(Redirected from MacLane'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).
[edit] References
- S. Mac Lane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937), 22–32.
