Mac Lane's planarity criterion

Last updated January 04, 2024

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 5$ 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 5$ 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 (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 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 $2 n - 5$ , the maximum possible number of bounded faces of a planar graph with the same vertex set ( Buhl et al. 2004 ).

Related Research Articles

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 cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In mathematics, a knot is an embedding of the circle $S 1$ into three-dimensional Euclidean space, $R 3$ . Often two knots are considered equivalent if they are ambient isotopic, that is, if there exists a continuous deformation of $R 3$ which takes one knot to the other.

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures in a one-to-one fashion, often by means of an involution operation: if the dual of $A$ is $B$ , then the dual of $B$ is $A$ . Such involutions sometimes have fixed points, so that the dual of $A$ is $A$ itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the $-dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.$

In the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In mathematics, more specifically in the field of ring theory, a ring R has the invariant basis number (IBN) property if all finitely generated free left modules over R have a well-defined rank. In the case of fields, the IBN property becomes the statement that finite-dimensional vector spaces have a unique dimension.

In algebraic geometry, a line bundle on a projective variety is nef if it has nonnegative degree on every curve in the variety. The classes of nef line bundles are described by a convex cone, and the possible contractions of the variety correspond to certain faces of the nef cone. In view of the correspondence between line bundles and divisors, there is an equivalent notion of a nef divisor.

In mathematics, linear maps form an important class of "simple" functions which preserve the algebraic structure of linear spaces and are often used as approximations to more general functions. If the spaces involved are also topological spaces, then it makes sense to ask whether all linear maps are continuous. It turns out that for maps defined on infinite-dimensional topological vector spaces, the answer is generally no: there exist discontinuous linear maps. If the domain of definition is complete, it is trickier; such maps can be proven to exist, but the proof relies on the axiom of choice and does not provide an explicit example.

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

<span class="mw-page-title-main">Peripheral cycle</span> Graph cycle which does not separate remaining elements

In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.

In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not.

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

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 expressed as a symmetric difference of basis cycles.

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs $K 5$ or $K 3,3$ , every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

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, Bibcode:2004EPJB...42..123B, doi:10.1140/epjb/e2004-00364-9, S2CID 14975826 .
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, MR 0652905 .
Lefschetz, Solomon (1965), "Planar graphs and related topics", Proceedings of the National Academy of Sciences of the United States of America, 54 (6): 1763–1765, Bibcode:1965PNAS...54.1763L, doi: 10.1073/pnas.54.6.1763 , JSTOR 72818, MR 0189011, PMC 300546 , PMID 16591326 .
Mac Lane, S. (1937), "A combinatorial condition for planar graphs" (PDF), Fundamenta Mathematicae, 28: 22–32, doi: 10.4064/fm-28-1-22-32 .
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 , hdl: 2060/19720020939 , JSTOR 2039496, MR 0313098 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.