Graph structure theorem
Encyclopedia
In mathematics, the graph structure theorem is a major result in the area of graph theory
. The result establishes a deep and fundamental connection between the theory of graph minors
and topological embeddings
. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson
and Paul Seymour. Accordingly, its proof is very long and involved. Articles and are surveys accessible to nonspecialist, describing the theorem and its consequences.
of a graph G is any graph H that is isomorphic to a graph that can be obtained from a subgraph of G by contracting
some edges. If G does not have a graph H as a minor, then we say that G is H-free. Let H be a fixed graph. Intuitively, if G is a huge H-free graph, then there ought to be a "good reason" for this. The graph structure theorem provides such a "good reason" in the form of a rough description of the structure of G. In essence, every H-free graph G suffers from one of two structural deficiencies: either G is "too thin" to have H as a minor, or G can be (almost) topologically embedded on a surface that is too simple for embed H upon. The first reason applies if H is a planar graph
, and both reasons apply if H is not planar. We first make precise these notions.
. Intuitively, a huge graph G has small tree width if and only if G takes the structure of a huge tree whose nodes and edges have been replaced by small graphs. We give a precise definition of tree width in the subsection regarding clique-sums. It is a theorem that if H is a minor of G, then the tree width of H is not greater than that of G. Therefore one "good reason" for G to be H-free is that the tree width of G is not very large. The graph structure theorem implies that this reason always applies in case H is planar.
Corollary 1. For every planar graph H, there exists a positive integer k such that every H-free graph has tree width less than k.
It is unfortunate that the value of k in Corollary 1 is generally much larger than the tree width of H (a notable exception is when H = K4, the complete graph on four vertices, for which k=3). This is one reason that the graph structure theorem is said to describe the "rough structure" of H-free graphs.
is a set of points which has a local topological structure of disc. Surfaces fall into two infinite families: the orientable surfaces include the sphere
, the torus
, the double torus
and so on; the nonorientable surfaces include the real projective plane
, the Klein bottle
and so on. A graph embeds
on a surface if the graph can be drawn on the surface as a set of points (vertices) and arcs (edges) which do cross or touch each other except where edges and vertices are incident or adjacent. A graph is planar
if it embeds on the sphere. If a graph G embeds on a particular surface then every minor of G also embeds on that same surface. Therefore, a "good reason" for G to be H-free is that G embeds on a surface that H does not embed on.
When H is not planar, the graph structure theorem may be regarded to be a vast generalization of the Kuratowski theorem. A version of this theorem proved by Wagner states that if a graph G is both K5-free and K3,3-free, then G is planar. This theorem provides a "good reason" for a graph G not to have K5 or K3,3 as minors; specifically, G embeds on the sphere, whereas neither K5 nor K3,3 embed on the sphere. Unfortunately, this notion of "good reason" is not sophisticated enough for the graph structure theorem. Two more notions are required: clique-sums and vortices.
Clique-sums
A clique
in a graph G is any set of vertices which are pairwise adjacent in G. For a non-negative integer k, a k-clique-sum of two graphs G and K is any graph obtained by selecting a non-negative integer m ≤ k, selecting clique of size m in each of G and K, identifying the two cliques into a single clique of size m, then deleting zero or more of the edges which join vertices in the new clique.
If G1, G2, ..., Gn is a list of graphs, then we may produce a new graph by joining the list of graphs via k-clique-sums. That is, we take a k-clique-sum of G1 and G2, then take a k-clique-sum of G3 with the resulting graph, and so on. A graph has tree width at most k if it can be obtained via k-clique-sums from a list of graphs, where each graph in the list has at most k + 1 vertices.
Corollary 1 indicates to us that k-clique-sums of small graphs describe the rough structure H-free graphs when H is planar. When H is nonplanar, we also need to consider k-clique-sums of a list of graphs, each of which is embedded on a surface. The following example with H = K5 illustrates this point. The graph K5 embeds on every surface except for the sphere. However there exist K5-free graphs which are far from being planar. In particular, the 3-clique-sum of any list of planar graphs results in a K5-free graph. Wagner determined the precise structure of K5-free graphs.
Theorem 2. If G is K5-free, then G can be obtained via 3-clique-sums from a list of planar graphs, and copies of one special non-planar graph having 8-vertices.
We point out that Theorem 2 is an exact structure theorem since the precise structure of K5-free graphs is determined. Such results are rare within graph theory. The graph structure theorem is not precise in this sense because, for most graphs H, the structural description of H-free graphs includes some graphs which are not H-free.
to each embedded graph in the list, we add at most k vortices, where each vortex has depth at most k
to each resulting graph we add at most k new vertices and add any number of edges, each having at least one of its endpoints among the new vertices.
finally, we join via k-clique-sums the resulting list of graphs.
Note that steps 1. and 2. result is an empty graph if H is planar, but the bounded number of vertices added in step 3. makes the statement consistent with Corollary 1.
, then every H-minor-free graph has a tree decomposition
of bounded width; equivalently, it can be represented as a clique-sum
of graphs of constant size When one of the graphs in H can be drawn in the plane with only a single crossing
, then the H-minor-free graphs admit a decomposition as a clique-sum of graphs of constant size and graphs of bounded genus, without vortices.
A different strengthening is also known when one of the graphs in H is an apex 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...
. The result establishes a deep and fundamental connection between the theory of graph minors
Minor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
and topological embeddings
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson
Neil Robertson (mathematician)
G. Neil Robertson is a mathematician working mainly in topological graph theory, currently a distinguished professor at the Ohio State University. He earned his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. According to the criteria of the Erdős Number...
and Paul Seymour. Accordingly, its proof is very long and involved. Articles and are surveys accessible to nonspecialist, describing the theorem and its consequences.
Setup and motivation for the theorem
A minorMinor (graph theory)
In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
of a graph G is any graph H that is isomorphic to a graph that can be obtained from a subgraph of G by contracting
Edge contraction
In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it previously connected. Edge contraction is a fundamental operation in the theory of graph minors...
some edges. If G does not have a graph H as a minor, then we say that G is H-free. Let H be a fixed graph. Intuitively, if G is a huge H-free graph, then there ought to be a "good reason" for this. The graph structure theorem provides such a "good reason" in the form of a rough description of the structure of G. In essence, every H-free graph G suffers from one of two structural deficiencies: either G is "too thin" to have H as a minor, or G can be (almost) topologically embedded on a surface that is too simple for embed H upon. The first reason applies if H is a 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...
, and both reasons apply if H is not planar. We first make precise these notions.
Tree width
The tree width of a graph G is a positive integer which specifies the "thinness" of G. For example, a connected graph G has tree width one if and only if it is a tree, and G has tree width two if and only if it is a series-parallel graphSeries-parallel graph
In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.-Definition and terminology:...
. Intuitively, a huge graph G has small tree width if and only if G takes the structure of a huge tree whose nodes and edges have been replaced by small graphs. We give a precise definition of tree width in the subsection regarding clique-sums. It is a theorem that if H is a minor of G, then the tree width of H is not greater than that of G. Therefore one "good reason" for G to be H-free is that the tree width of G is not very large. The graph structure theorem implies that this reason always applies in case H is planar.
Corollary 1. For every planar graph H, there exists a positive integer k such that every H-free graph has tree width less than k.
It is unfortunate that the value of k in Corollary 1 is generally much larger than the tree width of H (a notable exception is when H = K4, the complete graph on four vertices, for which k=3). This is one reason that the graph structure theorem is said to describe the "rough structure" of H-free graphs.
Surface embeddings
Roughly, a surfaceSurface
In mathematics, specifically in topology, a surface is a two-dimensional topological manifold. The most familiar examples are those that arise as the boundaries of solid objects in ordinary three-dimensional Euclidean space R3 — for example, the surface of a ball...
is a set of points which has a local topological structure of disc. Surfaces fall into two infinite families: the orientable surfaces include the sphere
Sphere
A sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...
, the torus
Torus
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...
, the double torus
Double torus
In mathematics, a genus-2 surface is a surface formed by the connected sum of two tori. That is to say, from each of two tori the interior of a disk is removed, and the boundaries of the two disks are identified , forming a double torus.This is the simplest case of the connected sum of n tori...
and so on; the nonorientable surfaces include the real projective plane
Real projective plane
In mathematics, the real projective plane is an example of a compact non-orientable two-dimensional manifold, that is, a one-sided surface. It cannot be embedded in our usual three-dimensional space without intersecting itself...
, the Klein bottle
Klein bottle
In mathematics, the Klein bottle is a non-orientable surface, informally, a surface in which notions of left and right cannot be consistently defined. Other related non-orientable objects include the Möbius strip and the real projective plane. Whereas a Möbius strip is a surface with boundary, a...
and so on. A graph embeds
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
on a surface if the graph can be drawn on the surface as a set of points (vertices) and arcs (edges) which do cross or touch each other except where edges and vertices are incident or adjacent. A graph is planar
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...
if it embeds on the sphere. If a graph G embeds on a particular surface then every minor of G also embeds on that same surface. Therefore, a "good reason" for G to be H-free is that G embeds on a surface that H does not embed on.
When H is not planar, the graph structure theorem may be regarded to be a vast generalization of the Kuratowski theorem. A version of this theorem proved by Wagner states that if a graph G is both K5-free and K3,3-free, then G is planar. This theorem provides a "good reason" for a graph G not to have K5 or K3,3 as minors; specifically, G embeds on the sphere, whereas neither K5 nor K3,3 embed on the sphere. Unfortunately, this notion of "good reason" is not sophisticated enough for the graph structure theorem. Two more notions are required: clique-sums and vortices.
Clique-sumsClique-sumIn graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology...
A cliqueClique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
in a graph G is any set of vertices which are pairwise adjacent in G. For a non-negative integer k, a k-clique-sum of two graphs G and K is any graph obtained by selecting a non-negative integer m ≤ k, selecting clique of size m in each of G and K, identifying the two cliques into a single clique of size m, then deleting zero or more of the edges which join vertices in the new clique.
If G1, G2, ..., Gn is a list of graphs, then we may produce a new graph by joining the list of graphs via k-clique-sums. That is, we take a k-clique-sum of G1 and G2, then take a k-clique-sum of G3 with the resulting graph, and so on. A graph has tree width at most k if it can be obtained via k-clique-sums from a list of graphs, where each graph in the list has at most k + 1 vertices.
Corollary 1 indicates to us that k-clique-sums of small graphs describe the rough structure H-free graphs when H is planar. When H is nonplanar, we also need to consider k-clique-sums of a list of graphs, each of which is embedded on a surface. The following example with H = K5 illustrates this point. The graph K5 embeds on every surface except for the sphere. However there exist K5-free graphs which are far from being planar. In particular, the 3-clique-sum of any list of planar graphs results in a K5-free graph. Wagner determined the precise structure of K5-free graphs.
Theorem 2. If G is K5-free, then G can be obtained via 3-clique-sums from a list of planar graphs, and copies of one special non-planar graph having 8-vertices.
We point out that Theorem 2 is an exact structure theorem since the precise structure of K5-free graphs is determined. Such results are rare within graph theory. The graph structure theorem is not precise in this sense because, for most graphs H, the structural description of H-free graphs includes some graphs which are not H-free.
Vortices (rough description)
One might be tempted to conjecture that an analog of Theorem 2 holds for graphs H other than K5. Perhaps it is true that: for any non-planar graph H, there exists a positive integer k such that every H-free graph can be obtained via k-clique-sums from a list of graphs, each of which either has at most k vertices or embeds on some surface that H does not embed on. Unfortunately, this statement is not yet sophisticated enough to be true. We must allow each embedded graph Gi to "cheat" in two limited ways. First, we must allow a bounded number of locations on the surface at which we may add some new vertices and edges which are permitted to cross each other in a manner of limited "complexity". Such locations are called vortices. The "complexity" of a vortex is limited by a parameter called its depth, closely related to pathwidth. The reader may prefer to defer reading the following precise description of a vortex of depth k. Second, we must allow a limited number of new vertices to be added to each of the embedded graphs with vortices.Vortices (precise definition)
A face of an embedded graph is an open 2-cell in the surface which is disjoint from the graph, but whose boundary is the union of some of the edges of the embedded graph. Let F be a face of an embedded graph G and let v0, v1, ... ,vn−1,vn = v0 be the vertices lying on the boundary of F (in that circular order). A circular interval for F is a set of vertices of the form {va, va+1, ... ,va+s} where a and k are integers and where subscripts are reduced modulo n. Let Λ be a finite list of circular intervals for F. We construct a new graph as follows. For each circular interval L in Λ we add a new vertex vL which is joined to zero or more of the vertices in L. Finally, for each pair {L, M} of intervals in Λ, we may add an edge joining vL to vM provided that L and M have nonempty intersection. The resulting graph is said to be obtained from G by adding a vortex of depth at most k (to the face F) provided that no vertex on the boundary of F appears in more than k of the intervals in Λ.Statement of the graph structure theorem
Graph structure theorem. For any graph H, there exists a positive integer k such that every H-free graph can be obtained as follows:Note that steps 1. and 2. result is an empty graph if H is planar, but the bounded number of vertices added in step 3. makes the statement consistent with Corollary 1.
Refinements
Strengthened versions of the graph structure theorem are possible depending on the set H of forbidden minors. For instance, when one of the graphs in H is planarPlanar 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...
, then every H-minor-free graph has a tree decomposition
Tree decomposition
In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to speed up solving certain problems on the original graph...
of bounded width; equivalently, it can be represented as a clique-sum
Clique-sum
In graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology...
of graphs of constant size When one of the graphs in H can be drawn in the plane with only a single crossing
Crossing number (graph theory)
In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...
, then the H-minor-free graphs admit a decomposition as a clique-sum of graphs of constant size and graphs of bounded genus, without vortices.
A different strengthening is also known when one of the graphs in H is an apex graph
Apex graph
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. We say an apex, not the apex because an apex graph may have more than one apex...
.