View source for Graph structure theorem

{{Short description|Theorem relating graph minors and topological embeddings}}
In [[Mathematics|mathematics]], the '''graph structure theorem''' is a major result in the area of [[Graph theory|graph theory]].  The result establishes a deep and fundamental connection between the theory of graph minors and [[Graph embedding|topological embeddings]]. The theorem is stated in the seventeenth of a series of 23 papers by [[Biography:Neil Robertson (mathematician)|Neil Robertson]] and Paul Seymour.  Its proof is very long and involved. {{harvtxt|Kawarabayashi|Mohar|2007}} and {{harvtxt|Lovász|2006}} are surveys accessible to nonspecialists, describing the theorem and its consequences.

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

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

''Corollary 1.'' For every planar graph {{mvar|H}}, there exists a positive integer {{mvar|k}} such that every {{mvar|H}}-free graph has tree width less than {{mvar|k}}.

It is unfortunate that the value of {{mvar|k}} in Corollary 1 is generally much larger than the tree width of {{mvar|H}} (a notable exception is when {{math|1=''H'' = ''K''{{sub|4}}}}, the complete graph on four vertices, for which {{math|1=''k'' = 3}}). This is one reason that the graph structure theorem is said to describe the "rough structure" of {{mvar|H}}-free graphs.

=== Surface embeddings ===
Roughly, a [[Surface (mathematics)|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|sphere]], the [[Torus|torus]], the double torus and so on; the ''nonorientable'' surfaces include the [[Real projective plane|real projective plane]], the [[Klein bottle]] and so on. A graph [[Graph embedding|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 graph|planar]] if it embeds on the sphere. If a graph {{mvar|G}} embeds on a particular surface then every minor of {{mvar|G}} also embeds on that same surface.  Therefore, a "good reason" for {{mvar|G}} to be {{mvar|H}}-free is that {{mvar|G}} embeds on a surface that {{mvar|H}} does not embed on.

When {{mvar|H}} 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 {{harvtxt|Wagner|1937}} states that if a graph {{mvar|G}} is both {{math|''K''{{sub|5}}}}-free and {{math|''K''{{sub|3,3}}}}-free, then {{mvar|G}} is planar.  This theorem provides a "good reason" for a graph {{mvar|G}} not to have {{math|''K''{{sub|5}}}} or {{math|''K''{{sub|3,3}}}} as minors; specifically, {{mvar|G}} embeds on the sphere, whereas neither {{math|''K''{{sub|5}}}} nor {{math|''K''{{sub|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-sum]]s ===
A [[Clique (graph theory)|clique]] in a graph {{mvar|G}} is any set of vertices that are pairwise adjacent in {{mvar|G}}. For a non-negative integer {{mvar|k}}, a '''{{mvar|k}}-clique-sum''' of two graphs {{mvar|G}} and {{mvar|K}} is any graph obtained by selecting a non-negative integer {{math|''m'' ≤ ''k''}}, selecting clique of size {{mvar|m}} in each of {{mvar|G}} and {{mvar|K}}, identifying the two cliques into a single clique of size {{mvar|m}}, then deleting zero or more of the edges that join vertices in the new clique.

If {{math|''G''{{sub|1}}, ''G''{{sub|2}}, …, ''G{{sub|n}}''}} is a list of graphs, then we may produce a new graph by joining the list of graphs ''via {{mvar|k}}-clique-sums''.  That is, we take a {{mvar|k}}-clique-sum of {{math|''G''{{sub|1}}}} and {{math|''G''{{sub|2}}}}, then take a {{mvar|k}}-clique-sum of {{math|''G''{{sub|3}}}} with the resulting graph, and so on.  A graph has '''tree width at most {{mvar|k}} ''' if it can be obtained via {{mvar|k}}-clique-sums from a list of graphs, where each graph in the list has at most {{math|''k'' + 1}} vertices.

Corollary 1 indicates to us that {{mvar|k}}-clique-sums of small graphs describe the rough structure {{mvar|H}}-free graphs when {{mvar|H}} is planar.  When {{mvar|H}} is nonplanar, we also need to consider {{mvar|k}}-clique-sums of a list of graphs, each of which is embedded on a surface. The following example with {{math|1=''H'' = {{math|''K''{{sub|5}}}}}} illustrates this point. The graph {{math|''K''{{sub|5}}}} embeds on every surface except for the sphere.  However there exist {{math|''K''{{sub|5}}}}-free graphs that are far from planar.  In particular, the 3-clique-sum of any list of planar graphs results in a {{math|''K''{{sub|5}}}}-free graph. {{harvtxt|Wagner|1937}} determined the precise structure of {{math|''K''{{sub|5}}}}-free graphs, as part of a cluster of results known as [[Wagner's theorem]]:

''Theorem 2.'' If {{mvar|G}} is {{math|''K''{{sub|5}}}}-free, then {{mvar|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 {{math|''K''{{sub|5}}}}-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 {{mvar|H}}, the structural description of {{mvar|H}}-free graphs includes some graphs that are ''not'' {{mvar|H}}-free.

=== Vortices (rough description) ===
One might be tempted to conjecture that an analog of Theorem 2 holds for graphs {{mvar|H}} other than {{math|''K''{{sub|5}}}}.  Perhaps it is true that: ''for any non-planar graph {{mvar|H}}, there exists a positive integer {{mvar|k}} such that every {{mvar|H}}-free graph can be obtained via {{mvar|k}}-clique-sums from a list of graphs, each of which either has at most {{mvar|k}} vertices or embeds on some surface that {{mvar|H}} does not embed on''.  Unfortunately, this statement is not yet sophisticated enough to be true.  We must allow each embedded graph {{mvar|G{{sub|i}}}} 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|pathwidth]].  The reader may prefer to defer reading the following precise description of a vortex of depth {{mvar|k}}.  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 {{mvar|F}} be a face of an embedded graph {{mvar|G}} and let {{math|''v''{{sub|0}}, ''v''{{sub|1}}, ..., ''v''{{sub|''n'' – 1}}}}, {{math|1=''v{{sub|n}}'' = ''v''{{sub|0}}}} be the vertices lying on the boundary of {{mvar|F}} (in that circular order).   A '''circular interval''' for {{mvar|F}} is a set of vertices of the form {{math|{''v''{{sub|''a''}}, ''v''{{sub|''a''+1}}, …, ''v''{{sub|''a''+''s''}}} }} where {{mvar|a}} and {{mvar|s}} are integers and where subscripts are reduced modulo {{mvar|n}}.  Let {{math|Λ}} be a finite list of circular intervals for {{mvar|F}}.  We construct a new graph as follows.  For each circular interval {{mvar|L}} in {{math|Λ}} we add a new vertex {{mvar|v{{sub|L}}}} that joins to zero or more of the vertices in {{mvar|L}}.  Finally, for each pair {{math|{''L'', ''M''} }} of intervals in {{math|Λ}}, we may add an edge joining {{mvar|v{{sub|L}}}} to {{mvar|v{{sub|M}}}} provided that {{mvar|L}} and {{mvar|M}} have nonempty intersection.  The resulting graph is said to be obtained from {{mvar|G}} by '''adding a vortex of depth at most {{mvar|k}} '''(to the face {{mvar|F}}) provided that no vertex on the boundary of {{mvar|F}} appears in more than {{mvar|k}} of the intervals in {{math|Λ}}.

== Statement of the graph structure theorem ==

'''Graph structure theorem.''' ''For any graph {{mvar|H}}, there exists a positive integer {{mvar|k}} such that every {{mvar|H}}-free graph can be obtained as follows:''
# ''We start with a list of graphs, where each graph in the list is embedded on a surface on which {{mvar|H}} does not embed''
# ''to each embedded graph in the list, we add at most {{mvar|k}} vortices, where each vortex has depth at most {{mvar|k}}
# ''to each resulting graph we add at most {{mvar|k}} new vertices (called [[Apex graph|apexes]]) and add any number of edges, each having at least one of its endpoints among the apexes.''
# ''finally, we join via {{mvar|k}}-clique-sums the resulting list of graphs.''

Note that steps 1. and 2. result in an empty graph if {{mvar|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 {{mvar|H}} of forbidden minors. For instance, when one of the graphs in {{mvar|H}} is [[Planar graph|planar]], then every {{mvar|H}}-minor-free graph has a [[Tree decomposition|tree decomposition]] of bounded width; equivalently, it can be represented as a [[Clique-sum|clique-sum]] of graphs of constant size.<ref>Graph Minors V.</ref> When one of the graphs in {{mvar|H}} can be drawn in the plane with only a single [[Crossing number (graph theory)|crossing]], then the {{mvar|H}}-minor-free graphs admit a decomposition as a clique-sum of graphs of constant size and graphs of bounded genus, without vortices.<ref>{{harvtxt|Robertson|Seymour|1993}}; {{harvtxt|Demaine|Hajiaghayi|Thilikos|2002}}).</ref>
A different strengthening is also known when one of the graphs in {{mvar|H}} is an [[Apex graph|apex graph]].<ref>{{harvtxt|Demaine|Hajiaghayi|Kawarabayashi|2009}}.</ref>

== See also ==
*[[Robertson–Seymour theorem]]

== Notes ==
{{reflist}}

== References ==
*{{citation
 | last2 = Hajiaghayi | first2 = Mohammad Taghi
 | contribution = Approximation algorithms via structural results for apex-minor-free graphs
 | doi = 10.1007/978-3-642-02927-1_27
 | pages = 316–327
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09)
 | url = http://erikdemaine.org/papers/ApexMinorFree_ICALP2009/paper.pdf
 | volume = 5555
 | year = 2009
 | mr = 2544855}}.
*{{citation
 | last2 = Hajiaghayi | first2 = Mohammad Taghi
 | last3 = Thilikos | first3 = Dimitrios M.
 | contribution = 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor
 | doi = 10.1007/3-540-45753-4_8
 | pages = 67–80
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002)
 | volume = 2462
 | year = 2002
 | mr = 2091577| hdl = 2117/97497
 | hdl-access = free
 }}.
*{{citation
 | doi = 10.1007/s00373-006-0684-x
 | issue = 1
 | journal = Graphs and Combinatorics
 | mr = 2292102
 | pages = 1–46
 | title = Some recent progress and applications in graph minor theory
 | volume = 23
 | year = 2007| s2cid = 7237484 }}.
*{{citation
 | doi = 10.1090/S0273-0979-05-01088-8
 | issue = 1
 | journal = [[Organization:Bulletin of the American Mathematical Society|Bulletin of the American Mathematical Society]]
 | mr = 2188176
 | pages = 75–86
 | title = Graph minor theory
 | volume = 43
 | year = 2006| doi-access = free
 }}.
*{{citation
 | doi = 10.1016/0095-8956(83)90079-5
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 723569
 | pages = 39–61
 | title = Graph minors. I. Excluding a forest
 | volume = 35
 | year = 1983| doi-access = free
 }}.
*{{citation
 | doi = 10.1016/0196-6774(86)90023-4
 | issue = 3
 | journal = Journal of Algorithms
 | mr = 855559
 | pages = 309–322
 | title = Graph minors. II. Algorithmic aspects of tree-width
 | volume = 7
 | year = 1986}}.
*{{citation
 | doi = 10.1016/0095-8956(84)90013-3
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 742386
 | pages = 49–64
 | title = Graph minors. III. Planar tree-width
 | volume = 36
 | year = 1984| doi-access = free
 }}.
*{{citation
 | doi = 10.1016/0095-8956(90)90120-O
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1046757
 | pages = 227–254
 | title = Graph minors. IV. Tree-width and well-quasi-ordering
 | volume = 48
 | year = 1990| doi-access = free
 }}.
*{{citation
 | doi = 10.1016/0095-8956(86)90030-4
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 854606
 | pages = 92–114
 | title = Graph minors. V. Excluding a planar graph
 | volume = 41
 | year = 1986| doi-access = free
 }}.
*{{citation
 | doi = 10.1016/0095-8956(86)90031-6
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 854607
 | pages = 115–138
 | title = Graph minors. VI. Disjoint paths across a disc
 | volume = 41
 | year = 1986| doi-access = 
 }}.
*{{citation
 | doi = 10.1016/0095-8956(88)90070-6
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 961150
 | pages = 212–254
 | title = Graph minors. VII. Disjoint paths on a surface
 | volume = 45
 | year = 1988| doi-access = 
 }}.
*{{citation
 | doi = 10.1016/0095-8956(90)90121-F
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1046758
 | pages = 255–288
 | title = Graph minors. VIII. A Kuratowski theorem for general surfaces
 | volume = 48
 | year = 1990| doi-access = 
 }}.
*{{citation
 | doi = 10.1016/0095-8956(90)90063-6
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1056819
 | pages = 40–77
 | title = Graph minors. IX. Disjoint crossed paths
 | volume = 49
 | year = 1990| doi-access = free
 }}.
*{{citation
 | doi = 10.1016/0095-8956(91)90061-N
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1110468
 | pages = 153–190
 | title = Graph minors. X. Obstructions to tree-decomposition
 | volume = 52
 | year = 1991| doi-access = free
 }}.
*{{citation
 | contribution = Excluding a graph with one crossing
 | editor1-last = Robertson | editor1-first = Neil
 | editor2-last = Seymour | editor2-first = Paul
 | pages = 669–675
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors
 | volume = 147
 | year = 1993
 | mr = 1224738
 | doi = 10.1090/conm/147/01206}}.
*{{citation
 | doi = 10.1006/jctb.1994.1007
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1256585
 | pages = 72–106
 | title = Graph minors. XI. Circuits on a surface
 | volume = 60
 | year = 1994| doi-access = free
 }}.
*{{citation
 | doi = 10.1006/jctb.1995.1034
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1339851
 | pages = 240–272
 | title = Graph minors. XII. Distance on a surface
 | volume = 64
 | year = 1995| doi-access = free
 }}.
*{{citation
 | doi = 10.1006/jctb.1995.1006
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1309358
 | pages = 65–110
 | title = Graph minors. XIII. The disjoint paths problem
 | volume = 63
 | year = 1995| doi-access = free
 }}.
*{{citation
 | doi = 10.1006/jctb.1995.1042
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1347339
 | pages = 23–50
 | title = Graph minors. XIV. Extending an embedding
 | volume = 65
 | year = 1995| doi-access = free
 }}.
*{{citation
 | doi = 10.1006/jctb.1996.0059
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1405708
 | pages = 112–148
 | title = Graph minors. XV. Giant steps
 | volume = 68
 | year = 1996| doi-access = free
 }}
*{{citation
 | doi = 10.1016/S0095-8956(03)00042-X
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1999736
 | pages = 43–76
 | title = Graph minors. XVI. Excluding a non-planar graph
 | volume = 89
 | year = 2003| doi-access = 
 }}.
*{{citation
 | doi = 10.1006/jctb.1999.1919
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1710538
 | pages = 162–210
 | title = Graph minors. XVII. Taming a vortex
 | volume = 77
 | year = 1999| doi-access = free
 }}.
*{{citation
 | doi = 10.1016/S0095-8956(03)00067-4
 | issue = 1
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 1999737
 | pages = 77–108
 | title = Graph minors. XVIII. Tree-decompositions and well-quasi-ordering
 | volume = 89
 | year = 2003| doi-access = 
 }}.
*{{citation
 | doi = 10.1016/j.jctb.2003.08.005
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 2034033
 | pages = 325–385
 | title = Graph minors. XIX. Well-quasi-ordering on a surface
 | volume = 90
 | year = 2004| doi-access = 
 }}.
*{{citation
 | doi = 10.1016/j.jctb.2004.08.001
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 2099147
 | pages = 325–357
 | title = Graph minors. XX. Wagner's conjecture
 | volume = 92
 | year = 2004| doi-access = free
 }}.
*{{citation
 | doi = 10.1016/j.jctb.2008.08.003
 | issue = 3
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 2507943
 | pages = 583–616
 | title = Graph minors. XXI. Graphs with unique linkages
 | volume = 99
 | year = 2009| doi-access = free
 }}.
*{{citation
 | title = Graph minors. XXII. Irrelevant vertices in linkage problems
 | volume = 102
 | issue = 2
 | pages = 530–563
 | journal = Journal of Combinatorial Theory | series = Series B
 | doi = 10.1016/j.jctb.2007.12.007
 | mr = 2885434
 | year = 2012| doi-access = free
 | url = http://www.math.princeton.edu/~pds/papers/GM22/GM22.pdf
 }}.
*{{citation
 | doi = 10.1016/j.jctb.2009.07.003
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 2595703
 | pages = 181–205
 | title = Graph minors XXIII. Nash-Williams' immersion conjecture
 | volume = 100
 | year = 2010| doi-access = free
 }}.
*{{citation
 | journal = Deutsche Mathematik
 | pages = 280–285
 | title = Über eine Erweiterung des Satzes von Kuratowski
 | volume = 2
 | year = 1937}}.

[[Category:Graph minor theory]]
[[Category:Theorems in graph theory]]

{{Sourceattribution|Graph structure theorem}}