Mac Lane's planarity criterion

From Wikipedia, the free encyclopedia
  (Redirected from MacLane's planarity criterion)
Jump to: navigation, search

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

Formal statement[edit]

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.

Proof[edit]

One direction of the characterisation is easy: if G is planar, then the set of boundaries of the bounded faces of a planar embedding of G form a basis of C(G). Clearly, each edge belongs to at most two such boundaries; 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. One way to prove that this set of boundaries forms a basis is by induction: if 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.

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 K5 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 K3,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 K5 and K3,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.

References[edit]