Graph structure theorem

The Robertson–Seymour theorem states that, for each fixed graph excluded as a minor, every graph excluding it can be assembled from graphs nearly embeddable on surfaces of bounded genus using clique-sums.

Connect

Graph minor: A graph obtained by deleting vertices or edges and contracting edges of another graph. The theorem classifies graph families by which fixed graph they exclude as a minor.
Nearly embeddable graph: A graph that can be embedded on a surface after boundedly many apices and bounded-width vortices are accounted for. These graphs are the structured pieces combined by clique-sums.
Paul Seymour: An American mathematician whose work includes major contributions to graph theory and combinatorics. He co-developed the graph-minor theory underlying the structure theorem.
Minor-closed graph family: A class of graphs closed under taking vertex deletions, edge deletions, and edge contractions. The theorem describes the structure of classes defined by excluding fixed minors.
Grid minor theorem: A theorem relating sufficiently large treewidth to the presence of a large grid as a minor. Quantitative grid-minor bounds shape how effectively structural decompositions can be used.
Clique-sum: An operation that glues graphs along cliques, possibly deleting edges within the shared clique. Clique-sums are the assembly operation in the theorem’s structural description.
Vortex (graph theory): A graph region attached along a face whose vertices admit a path decomposition of bounded width. Vortices capture bounded-width regions that prevent a piece from being fully embedded.
Neil Robertson: A mathematician known for foundational work in graph minors and structural graph theory. He co-developed the theorem and the surrounding graph-minor program.
Fixed-parameter tractability: An algorithmic regime in which runtime is polynomial in input size for each fixed parameter value. Structural decomposition enables efficient algorithms for many problems on excluded-minor classes.
Excluded grid theorem: The result that graphs of sufficiently large treewidth contain arbitrarily large grid minors. Its bounds are a major quantitative companion to the structure theorem.