Mac Lane's planarity criterion
Encyclopedia
In graph theory
, Mac Lane's planarity criterion is a characterisation of planar graph
s in terms of their cycle space
s. It states that a finite undirected graph is planar if and only if
the cycle space of the graph (taken modulo 2) has a basis
in which each edge of the graph participates in at most two basis vectors.
with two elements; that is, in this vector space, vectors are added coordinatewise modulo two. A 2-basis of is a basis of with the property that, for each edge in , at most two basis vectors have nonzero coordinates in the position corresponding to . Then, stated more formally, Mac Lane's characterization is that the planar graphs are exactly the graphs that have a 2-basis.
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). However, the complete graph
has no 2-basis: is seven-dimensional, and each nontrivial vector in has nonzero coordinates for at least three edges, so any 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
has no 2-basis: is five-dimensional, and each nontrivial vector in has nonzero coordinates for at least four edges, so any 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 and , it is also not true of any other nonplanar graph.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, Mac Lane's planarity criterion is a characterisation of planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s in terms of their cycle space
Cycle space
In graph theory, an area of mathematics, a cycle space is a vector space defined from an undirected graph; elements of the cycle space represent formal combinations of cycles in the graph....
s. It states that a finite undirected graph is planar if and only if
the cycle space of the graph (taken modulo 2) has a basis
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
in which each edge of the graph participates in at most two basis vectors.
Formal statement
For any cycle in a graph , one can form an -dimensional 0-1 vector that has a 1 in the coordinate positions corresponding to edges in and a 0 in the remaining coordinate positions. The cycle space of the graph is the vector space formed by all possible linear combinations of vectors formed in this way. In Mac Lane's characterization, is a vector space over the finite fieldFinite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
with two elements; that is, in this vector space, vectors are added coordinatewise modulo two. A 2-basis of is a basis of with the property that, for each edge in , at most two basis vectors have nonzero coordinates in the position corresponding to . Then, stated more formally, Mac Lane's characterization is that the planar graphs are exactly the graphs that have a 2-basis.
Proof
One direction of the characterisation is easy: if is planar, then the set of boundaries of the bounded faces of a planar embedding of form a basis of . Clearly, each edge belongs to at most two such boundaries; if an edge is a bridge of , 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 is a tree, then it has no bounded faces and is zero-dimensional and has an empty basis. Otherwise, removing an edge from the unbounded face of reduces both the dimension of the cycle space and the number of bounded faces by one.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). However, the complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
has no 2-basis: is seven-dimensional, and each nontrivial vector in has nonzero coordinates for at least three edges, so any 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
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
has no 2-basis: is five-dimensional, and each nontrivial vector in has nonzero coordinates for at least four edges, so any 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 and , it is also not true of any other nonplanar graph.