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 graphs in terms of their cycle spaces, 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 modulo 2) has a cycle basis in which each edge of the graph participates in at most two basis vectors.

Statement

For any cycle c in a graph G, one can form an m-dimensional 0-1 vector that has a 1 in the coordinate positions corresponding to edges in c and a 0 in the remaining coordinate positions. The cycle space 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, C(G) is a vector space over the finite field GF(2) with two elements; that is, in this vector space, vectors are added coordinatewise modulo two. A 2-basis of G is a basis of C(G) with the property that, for each edge e in G, at most two basis vectors have nonzero coordinates in the position corresponding to 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 G.

If an edge is a bridge of 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 induction. As a base case, G is a tree, then it has no bounded faces and C(G) is zero-dimensional and has an empty basis. Otherwise, removing an edge from the unbounded face of 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's formula to show that the number of cycles in this collection equals the circuit rank of 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 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

(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 minors. As O'Neill observes, the property of having a 2-basis is preserved under graph minors: 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 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 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 K₅ has no 2-basis: C(G) is six-dimensional, each nontrivial vector in 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 K_3,3 has no 2-basis: C(G) is four-dimensional, and each nontrivial vector in 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 K₅ and K_3,3, it is also not true of any other nonplanar graph.

(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 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

(Ja'Ja' Simon) 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 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 cycles 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 2n − 5, the maximum possible number of bounded faces of a planar graph with the same vertex set (Buhl Gautrais).

References

• Buhl, J.; Gautrais, J.; Sole, R.V.; Kuntz, P.; Valverde, S.; Deneubourg, J.L.; Theraulaz, G. (2004), "Efficiency and robustness in ant networks of galleries", The European Physical Journal B (Springer-Verlag) 42 (1): 123–129, doi:10.1140/epjb/e2004-00364-9, Bibcode: 2004EPJB...42..123B .
• Ja'Ja', Joseph; Simon, Janos (1982), "Parallel algorithms in graph theory: planarity testing", SIAM Journal on Computing 11 (2): 314–328, doi:10.1137/0211024 .
• "Planar graphs and related topics", Proceedings of the National Academy of Sciences of the United States of America 54 (6): 1763–1765, 1965, doi:10.1073/pnas.54.6.1763, PMID 16591326, Bibcode: 1965PNAS...54.1763L .
• "A combinatorial condition for planar graphs", Fundamenta Mathematicae 28: 22–32, 1937, doi:10.4064/fm-28-1-22-32, http://matwbn.icm.edu.pl/ksiazki/fm/fm28/fm2814.pdf .
• O'Neil, P. V. (1973), "A short proof of Mac Lane's planarity theorem", Proceedings of the American Mathematical Society 37 (2): 617–618, doi:10.1090/S0002-9939-1973-0313098-X .