Graph structure theorem

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. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

A minor 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 to 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.

The tree width of a graph G is a positive integer that 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 graph. 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.

...
Wikipedia