View source for Mac Lane's planarity criterion

{{Short description|On cycle bases of planar graphs}}
In [[graph theory]], '''Mac Lane's planarity criterion''' is a characterisation of [[planar graph]]s in terms of their [[cycle space]]s, named after [[Saunders Mac Lane]] who published it in 1937. It states that a finite [[undirected graph]] is planar if and only if 
the cycle space of the graph (taken [[modular arithmetic|modulo]] 2) has a [[cycle basis]] in which each edge of the graph participates in at most two [[basis vector]]s.

==Statement==
For any cycle {{mvar|c}} in a graph {{mvar|G}} on {{mvar|m}} edges, one can form an {{mvar|m}}-dimensional 0-1 vector that has a 1 in the coordinate positions corresponding to edges in {{mvar|c}} and a 0 in the remaining coordinate positions. The cycle space {{math|''C''(''G'')}} of the graph is the [[vector space]] formed by all possible linear combinations of vectors formed in this way. In Mac Lane's characterization, {{math|''C''(''G'')}} is a vector space over the [[finite field]] {{math|GF(2)}} with two elements; that is, in this vector space, vectors are added coordinatewise modulo two. A ''2-basis'' of {{mvar|G}} is a basis of {{math|''C''(''G'')}} with the property that, for each edge {{mvar|e}} in {{mvar|G}}, at most two basis vectors have nonzero coordinates in the position corresponding to {{mvar|e}}. Then, stated more formally, Mac Lane's characterization is that the planar graphs are exactly the graphs that have a 2-basis.

==Existence of a 2-basis for planar graphs==
One direction of the characterisation states that every planar graph has a 2-basis. Such a basis may be found as the collection of boundaries of the bounded faces of a [[planar embedding]] of the given graph {{mvar|G}}.

If an edge is a bridge of {{mvar|G}}, it appears twice on a single face boundary and therefore has a zero coordinate in the corresponding vector. Thus, the only edges that have nonzero coordinates are the ones that separate two different faces; these edges appear either once (if one of the faces is the unbounded one) or twice in the collection of boundaries of bounded faces. It remains to prove that these cycles form a basis. One way to prove this by [[mathematical induction|induction]]. As a base case, {{mvar|G}} is a tree, then it has no bounded faces and {{math|''C''(''G'')}} is zero-dimensional and has an empty basis. Otherwise, removing an edge from the unbounded face of {{mvar|G}} reduces both the dimension of the cycle space and the number of bounded faces by one and the induction follows.

Alternatively, it is possible to use [[Euler characteristic|Euler's formula]] to show that the number of cycles in this collection equals the [[circuit rank]] of {{mvar|G}}, which is the dimension of the cycle space. Each nonempty subset of cycles has a vector sum that represents the boundary of the union of the bounded faces in the subset, which cannot be empty (the union includes at least one bounded face and excludes the unbounded face, so there must be some edges separating them). Therefore, there is no subset of cycles whose vectors sum to zero, which means that all the cycles are [[linear independence|linearly independent]]. As a linearly independent set of the same size as the dimension of the space, this collection of cycles must form a basis.

==Necessity of planarity when a 2-basis exists==
{{harvtxt|O'Neil|1973}} provided the following simple argument for the other direction of the characterization, based on [[Wagner's theorem]] characterizing the planar graphs by [[forbidden minor]]s. As O'Neill observes, the property of having a 2-basis is preserved under [[graph minor]]s: if one contracts an edge, the same contraction may be performed in the basis vectors, if one removes an edge that has a nonzero coordinate in a single basis vector, then that vector may be removed from the basis, and if one removes an edge that has a nonzero coordinate in two basis vectors, then those two vectors may be replaced by their sum (modulo two). Additionally, if {{math|''C''(''G'')}} is a cycle basis for any graph, then it must cover some edges exactly once, for otherwise its sum would be zero (impossible for a basis), and so {{math|''C''(''G'')}} can be augmented by one more cycle consisting of these singly-covered edges while preserving the property that every edge is covered at most twice.
However, the [[complete graph]] {{math|''K''<sub>5</sub>}} has no 2-basis: {{math|''C''(''G'')}} is six-dimensional, each nontrivial vector in  {{math|''C''(''G'')}} has nonzero coordinates for at least three edges, and so any augmented basis would have at least 21 nonzeros, exceeding the 20 nonzeros that would be allowed if each of the ten edges were nonzero in at most two basis vectors. By similar reasoning, the [[complete bipartite graph]] {{math|''K''<sub>3,3</sub>}} has no 2-basis: {{math|''C''(''G'')}} is four-dimensional, and each nontrivial vector in  {{math|''C''(''G'')}} has nonzero coordinates for at least four edges, so any augmented basis would have at least 20 nonzeros, exceeding the 18 nonzeros that would be allowed if each of the nine edges were nonzero in at most two basis vectors. Since the property of having a 2-basis is minor-closed and is not true of the two minor-minimal nonplanar graphs {{math|''K''<sub>5</sub>}} and {{math|''K''<sub>3,3</sub>}}, it is also not true of any other nonplanar graph.

{{harvtxt|Lefschetz|1965}} provided another proof, based on [[algebraic topology]]. He uses a slightly different formulation of the planarity criterion, according to which a graph is planar if and only if it has a set of (not necessarily simple) cycles covering every edge exactly twice, such that the only nontrivial relation among these cycles in {{math|''C''(''G'')}} is that their sum be zero. If this is the case, then leaving any one of the cycles out produces a basis satisfying Mac Lane's formulation of the criterion. If a planar graph is embedded on a sphere, its face cycles clearly satisfy Lefschetz's property. Conversely, as Lefschetz shows, whenever a graph ''G'' has a set of cycles with this property, they necessarily form the face cycles of an embedding of the graph onto the sphere.

==Application==
{{harvtxt|Ja'Ja'|Simon|1982}} used Mac Lane's planarity criterion as part of a [[parallel algorithm]] for testing graph planarity and finding planar embeddings. Their algorithm partitions the graph into [[SPQR tree|triconnected components]], after which there is a unique planar embedding (up to the choice of the outer face) and the cycles in a 2-basis can be assumed to be all the [[peripheral cycle]]s of the graph. Ja'Ja' and Simon start with a fundamental cycle basis of the graph (a cycle basis generated from a [[spanning tree]] by forming a cycle for each possible combination of a path in the tree and an edge outside the tree) and transform it into a 2-basis of peripheral cycles. These cycles form the faces of a planar embedding of the given graph.

Mac Lane's planarity criterion allows the number of bounded face cycles in a planar graph to be counted easily, as the [[circuit rank]] of the graph. This property is used in defining the [[meshedness coefficient]] of the graph, a normalized variant of the number of bounded face cycles that is computed by dividing the circuit rank by {{math|2''n''&nbsp;&minus;&nbsp;5}}, the maximum possible number of bounded faces of a planar graph with the same vertex set {{harv|Buhl|Gautrais|Sole|Kuntz|2004}}.

==References==
*{{citation
 | last1 = Buhl | first1 = J.
 | last2 = Gautrais | first2 = J.
 | last3 = Sole | first3 = R.V.
 | last4 = Kuntz | first4 = P.
 | last5 = Valverde | first5 = S.
 | last6 = Deneubourg | first6 = J.L.
 | last7 = Theraulaz | first7 = G.
 | doi = 10.1140/epjb/e2004-00364-9
 | issue = 1
 | journal = The European Physical Journal B
 | pages = 123–129
 | publisher = Springer-Verlag
 | title = Efficiency and robustness in ant networks of galleries
 | volume = 42
 | year = 2004| bibcode = 2004EPJB...42..123B
 | s2cid = 14975826
 }}.
*{{citation
 | last1 = Ja'Ja' | first1 = Joseph
 | last2 = Simon | first2 = Janos
 | doi = 10.1137/0211024
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | mr = 652905
 | pages = 314–328
 | title = Parallel algorithms in graph theory: planarity testing
 | volume = 11
 | year = 1982}}.
*{{citation
 | last = Lefschetz | first = Solomon | author-link = Solomon Lefschetz
 | doi = 10.1073/pnas.54.6.1763
 | journal = Proceedings of the National Academy of Sciences of the United States of America
 | jstor = 72818
 | mr = 0189011
 | pages = 1763–1765
 | title = Planar graphs and related topics
 | volume = 54
 | issue = 6 | year = 1965| pmc = 300546 | pmid=16591326| bibcode = 1965PNAS...54.1763L | doi-access = free }}.
*{{citation
 | last = Mac Lane | first = S. | author-link = Saunders Mac Lane
 | journal = Fundamenta Mathematicae
 | pages = 22–32
 | title = A combinatorial condition for planar graphs
 | url = http://matwbn.icm.edu.pl/ksiazki/fm/fm28/fm2814.pdf
 | volume = 28
 | year = 1937| doi = 10.4064/fm-28-1-22-32 | doi-access = free
 }}.
*{{citation
 | last = O'Neil | first = P. V.
 | journal = Proceedings of the American Mathematical Society
 | doi = 10.1090/S0002-9939-1973-0313098-X
 | jstor = 2039496
 | mr = 0313098
 | pages = 617–618
 | title = A short proof of Mac Lane's planarity theorem
 | volume = 37
 | issue = 2
 | year = 1973| hdl = 2060/19720020939
 | doi-access = free
 | hdl-access = free
 }}.

[[Category:Algebraic graph theory]]
[[Category:Statements about planar graphs]]