Graph structure theorem

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.

Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

The graph structure theorem implies that this reason always applies in case H is planar.

Roughly, a surface is a set of points with a local topological structure of a disc.

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.

Unfortunately, this notion of "good reason" is not sophisticated enough for the graph structure theorem.

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.

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 add to each of the embedded graphs with vortices.

A circular interval for F is a set of vertices of the form {va, va+1, …, va+s} where a and s 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 that joins 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.

Strengthened versions of the graph structure theorem are possible depending on the set H of forbidden minors.