Graph structure theorem

Template:Short description 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. Its proof is very long and involved. and are surveys accessible to nonspecialists, describing the theorem and its consequences.

Setup and motivation for the theorem

A minor of a graph Template:Mvar is any graph Template:Mvar that is isomorphic to a graph that can be obtained from a subgraph of Template:Mvar by contracting some edges. If Template:Mvar does not have a graph Template:Mvar as a minor, then we say that Template:Mvar is Template:Mvar-free. Let Template:Mvar be a fixed graph. Intuitively, if Template:Mvar is a huge Template:Mvar-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 Template:Mvar. In essence, every Template:Mvar-free graph Template:Mvar suffers from one of two structural deficiencies: either Template:Mvar is "too thin" to have Template:Mvar as a minor, or Template:Mvar can be (almost) topologically embedded on a surface that is too simple to embed Template:Mvar upon. The first reason applies if Template:Mvar is a planar graph, and both reasons apply if Template:Mvar is not planar. We first make precise these notions.

Tree width

The tree width of a graph Template:Mvar is a positive integer that specifies the "thinness" of Template:Mvar. For example, a connected graph Template:Mvar has tree width one if and only if it is a tree, and Template:Mvar has tree width two if and only if it is a series–parallel graph. Intuitively, a huge graph Template:Mvar has small tree width if and only if Template:Mvar 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 Template:Mvar is a minor of Template:Mvar, then the tree width of Template:Mvar is not greater than that of Template:Mvar. Therefore, one "good reason" for Template:Mvar to be Template:Mvar-free is that the tree width of Template:Mvar is not very large. The graph structure theorem implies that this reason always applies in case Template:Mvar is planar.

Corollary 1. For every planar graph Template:Mvar, there exists a positive integer Template:Mvar such that every Template:Mvar-free graph has tree width less than Template:Mvar.

It is unfortunate that the value of Template:Mvar in Corollary 1 is generally much larger than the tree width of Template:Mvar (a notable exception is when H = K₄, 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 Template:Mvar-free graphs.

Surface embeddings

Roughly, a surface is a set of points with a local topological structure of a 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) that do not 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 Template:Mvar embeds on a particular surface then every minor of Template:Mvar also embeds on that same surface. Therefore, a "good reason" for Template:Mvar to be Template:Mvar-free is that Template:Mvar embeds on a surface that Template:Mvar does not embed on.

When Template:Mvar is not planar, the graph structure theorem may be looked at as a vast generalization of the Kuratowski theorem. A version of this theorem proved by states that if a graph Template:Mvar is both K₅-free and K_3,3-free, then Template:Mvar is planar. This theorem provides a "good reason" for a graph Template:Mvar not to have K₅ or K_3,3 as minors; specifically, Template:Mvar embeds on the sphere, whereas neither K₅ nor K_3,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 Template:Mvar is any set of vertices that are pairwise adjacent in Template:Mvar. For a non-negative integer Template:Mvar, a Template:Mvar-clique-sum of two graphs Template:Mvar and Template:Mvar is any graph obtained by selecting a non-negative integer m ≤ k, selecting clique of size Template:Mvar in each of Template:Mvar and Template:Mvar, identifying the two cliques into a single clique of size Template:Mvar, then deleting zero or more of the edges that join vertices in the new clique.

If G₁, G₂, …, G_n is a list of graphs, then we may produce a new graph by joining the list of graphs via Template:Mvar-clique-sums. That is, we take a Template:Mvar-clique-sum of G₁ and G₂, then take a Template:Mvar-clique-sum of G₃ with the resulting graph, and so on. A graph has tree width at most Template:Mvar if it can be obtained via Template:Mvar-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 Template:Mvar-clique-sums of small graphs describe the rough structure Template:Mvar-free graphs when Template:Mvar is planar. When Template:Mvar is nonplanar, we also need to consider Template:Mvar-clique-sums of a list of graphs, each of which is embedded on a surface. The following example with H = K₅ illustrates this point. The graph K₅ embeds on every surface except for the sphere. However, there exist K₅-free graphs that are far from planar. In particular, the 3-clique-sum of any list of planar graphs results in a K₅-free graph. determined the precise structure of K₅-free graphs, as part of a cluster of results known as Wagner's theorem:

Theorem 2. If Template:Mvar is K₅-free, then Template:Mvar 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 K₅-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 Template:Mvar, the structural description of Template:Mvar-free graphs includes some graphs that are not Template:Mvar-free.

Vortices (rough description)

One might be tempted to conjecture that an analog of Theorem 2 holds for graphs Template:Mvar other than K₅. Perhaps it is true that: for any non-planar graph Template:Mvar, there exists a positive integer Template:Mvar such that every Template:Mvar-free graph can be obtained via Template:Mvar-clique-sums from a list of graphs, each of which either has at most Template:Mvar vertices or embeds on some surface that Template:Mvar does not embed on. Unfortunately, this statement is not yet sophisticated enough to be true. We must allow each embedded graph Template:Mvar 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 that 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 Template:Mvar. Second, we must allow a limited number of new vertices to add 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 that is disjoint from the graph, but whose boundary is the union of some of the edges of the embedded graph. Let Template:Mvar be a face of an embedded graph Template:Mvar and let v₀, v₁, ..., v_{n – 1}, v_n = v₀ be the vertices lying on the boundary of Template:Mvar (in that circular order). A circular interval for Template:Mvar is a set of vertices of the form {v_a, v_a+1, …, v_a+s} where Template:Mvar and Template:Mvar are integers and where subscripts are reduced modulo Template:Mvar. Let Λ be a finite list of circular intervals for Template:Mvar. We construct a new graph as follows. For each circular interval Template:Mvar in Λ we add a new vertex Template:Mvar that joins to zero or more of the vertices in Template:Mvar. Finally, for each pair {L, M} of intervals in Λ, we may add an edge joining Template:Mvar to Template:Mvar provided that Template:Mvar and Template:Mvar have nonempty intersection. The resulting graph is said to be obtained from Template:Mvar by adding a vortex of depth at most Template:Mvar (to the face Template:Mvar) provided that no vertex on the boundary of Template:Mvar appears in more than Template:Mvar of the intervals in Λ.

Statement of the graph structure theorem

Graph structure theorem. For any graph Template:Mvar, there exists a positive integer Template:Mvar such that every Template:Mvar-free graph can be obtained as follows:

1. We start with a list of graphs, where each graph in the list is embedded on a surface on which Template:Mvar does not embed
2. to each embedded graph in the list, we add at most Template:Mvar vortices, where each vortex has depth at most Template:Mvar
3. to each resulting graph we add at most Template:Mvar new vertices (called apices) and add any number of edges, each having at least one of its endpoints among the apices.
4. finally, we join via Template:Mvar-clique-sums the resulting list of graphs.

Note that steps 1. and 2. result in an empty graph if Template:Mvar 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 Template:Mvar of forbidden minors. For instance, when one of the graphs in Template:Mvar is planar, then every Template:Mvar-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 Template:Mvar can be drawn in the plane with only a single crossing, then the Template:Mvar-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 Template:Mvar is an apex graph.

See also

• Robertson–Seymour theorem

References

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .