graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, Mac Lane's planarity criterion is a characterisation of

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. In other words, it can be drawn in such a way that no edges cro ...

s in terms of their

cycle space In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs. This set of subgraphs can be described algebraically as a vector space over the two-element finite field. The dime ...

s, named after

Saunders Mac Lane Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg. Early life and education Mac Lane was born in Norwich, Connecticut, near where his family lived in Taftvill ...

, who published it in 1937. It states that a finite

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is planar if and only if the cycle space of the graph (taken modulo 2) has a

cycle basis In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expr ...

in which each edge of the graph participates in at most two basis vectors.

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 field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...

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.

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 . 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. 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, 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 and the induction follows. Alternatively, it is possible to use

Euler's formula Euler's formula, named after Leonhard Euler, is a mathematical formula in complex analysis that establishes the fundamental relationship between the trigonometric functions and the complex exponential function. Euler's formula states that for ...

to show that the number of cycles in this collection equals the

circuit rank In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycle (graph theory), cycles, making ...

of , 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 In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts ...

. 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

provided the following simple argument for the other direction of the characterization, based on

Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on f ...

characterizing the planar graphs by

forbidden minor In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...

s. As O'Neill observes, the property of having a 2-basis is preserved under

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...

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 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 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 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. A complete digraph is a directed graph in which every pair of distinct vertices ...

has no 2-basis: is six-dimensional, each nontrivial vector in 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 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..Electronic edition page 17. Graph theory ...

has no 2-basis: is four-dimensional, and each nontrivial vector in 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 and , it is also not true of any other nonplanar graph. provided another proof, based on

algebraic topology Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism, though usually most classif ...

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

used Mac Lane's planarity criterion as part of a

parallel algorithm In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machine ...

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 cycle In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygo ...

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 In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

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

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 , the maximum possible number of bounded faces of a planar graph with the same vertex set .

References

*. *. *. *. *{{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 . Algebraic graph theory Planar graphs