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).
References
- S. Mac Lane, A combinatorial condition for planar graphs, Fund. Math. 28 (1937), 22–32.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
