Mac Lane's planarity criterion

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

References

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Cycle space — This article is about a concept in graph theory. For space allocated to bicycles, see segregated cycle facilities. In graph theory, an area of mathematics, a cycle space is a vector space defined from an undirected graph; elements of the cycle… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”