
In my book (available at publisher's site) I present a comprehensive development of the structural theory of graph minors and illustrate the applications of this theory on a number of examples.
- Part I: Understanding the Structure Theorem
- Tree Decompositions and Treewidth (72 pages)
Review of basic results on tree decompositions, treewidth, and obstructions to bounded treewidth (unbreakable sets, tangles, brambles, grid minors and wall subdivisions). Grid Theorem and its proof, Erdős-Pósa theory. More detailed development of the theory of tangles and especially of respectful tangles arising in graphs on surfaces.
- Linkedness (18 pages)
When we construct pieces of an object in different parts of a graph, how can we link these pieces together by vertex-disjoint paths? The notion of k-linked graphs, linkedness in graphs containing a large clique minor and in graphs of large connectivity. Unique Linkage Theorem and its usage to identify vertices irrelevant for the existence of a linkage. Linked tree decompositions.
- Graphs on Surfaces (52 pages)
Given a graph on a surface, which small graphs appear in it as (rooted) minors? We address this important question by presenting a natural sufficient condition in terms of absence of topological and connectivity obstructions. A further development of the theory of respectful tangles, especially in connection to the derived metric in graphs on surfaces, gives us a convenient language to express this condition.
- Towards the Structure Theorem (50 pages)
We proceed on our way towards the proof of the Structure Theorem. We study the structure of graphs drawn in the disk up to a single exceptional region where crossings can occur, and see how the vortices arise. As a mid-point, we prove Flat Wall Theorem and explain its application in a polynomial-time algorithm to test the presence of a fixed graph as a minor. We finish with an explanation of the rest of the ideas that go to the proof of the full Structure Theorem.
- Tree Decompositions and Treewidth (72 pages)
- Part II: Using the Structure Theorem
- Low-Treewidth Colorings (16 pages)
An example of a standard application of the Structure Theorem, illustrating the issues essentially all applications need to deal with (handling apices and vortices, proving a more general result to deal with the clique-sums). Discussion of applications of treewidth-fragility, a useful property not restricted just to proper minor-closed classes, especially concerning chromatic number approximation. Further application of the Structure Theorem to show that every graph avoiding a fixed minor and a bipartite subgraph can be divided into a part with bounded treewidth and a part with bounded degeneracy; this is used to obtain approximation algorithm for chromatic number with additive error, but also showcases a common technique for restricting apices.
- Tighter Grid Theorem (8 pages)
A slightly more involved application showing a common way of dealing with the surface part of the decomposition. A brief introduction into the theory of bidimensionality, which exploits the fact that graphs avoiding a fixed minor contain grids whose sides have length linear in treewidth (and thus they contain quadratically many vertices in treewidth) to reduce time complexity of parameterized algorithms.
- Topological Minors (22 pages)
A more technically challenging application, where the possibility to use the theory of graph minors arises from the fact that the considered problem is relatively easy to handle in graphs containing a large clique minors. Dealing with the complementary case for graphs avoiding the clique minor requires the use of the local form of the Structure Theorem and shows a useful idea to streamline an argument by turning inconvenient regions of the surface part into new vortices. Another common technique showcased is the usage of Erdős-Pósa style results to show that either a desired structure is ubiquitous and we can link to many disjoint copies, or all such structures can be cut off by a small separation. On the high-level, we present the fundamentals of the recently developed structural theory of graphs avoiding a fixed topological minor.
- Minors in Large Connected Graphs (28 pages)
The most technically demanding application, requiring us to present a more detailed technical analysis of the structure of vortices. We show that it is possible to make the width of the vortices uniform across their whole length and to link through them by many disjoint paths. We explain why in sufficiently dense graphs avoiding a fixed minor, we are guaranteed to find a long vortex, and we use the ideas from
Linkedness
chapter to show that such vortices contain interesting minors. We discuss the applications of the final result in algorithms related to Hadwiger's conjecture.
- Low-Treewidth Colorings (16 pages)
- Part III: Avoiding the Structure Theorem
- Sublinear Separators (8 pages)
We present a direct proof that graphs avoiding a fixed minor have balanced separators of sublinear size, and explore the algorithmic implications of this result.
- Chordal Partitions (12 pages)
We show a useful technique of contracting the graph (without any further assumptions) to obtain its chordal minor, then exploit the fact that if the original graph does not contain a fixed minor, then its chordal minor has bounded treewidth. As examples of applications of the technique, we give a proof of fractional linear Hadwiger's conjecture and give bounds on interesting degeneracy-type parameters.
- Chromatic Number (18 pages)
We survey the progress towards Hadwiger's conjecture and present some of the ideas that go into the recent improved bounds on the chromatic number of graphs avoiding a fixed minor. We discuss the relationship of these results to the density of graphs from proper minor-closed classes, and we present a simple proof of the asymptotically tight upper bound on the density. We also consider relaxed versions of Hadwiger's conjecture (defective and clustered coloring), showcasing another application of the chordal partitions method.
- Product Structure (18 pages)
We present the surprising recent result that planar graphs are subgraphs of the strong product of a path and a graph of bounded treewidth, and derive a related
rough but simple
form of the structure theorem for proper minor-closed classes. We show an example application to the non-repetitive colorings. - Iterated Layerings (20 pages)
The breadth-first search layering in planar graphs has the property that the union of a bounded number of layers has bounded treewidth; this is the basis of a powerful method by Baker for designing polynomial-time approximation schemes. We show how to generalize this method to all proper minor-closed classes by iterating the layering idea. We also present a related result of Klein, Plotkin, and Rao important in the theory of multicommodity flows and metric embeddings.
- Isomorphism Testing (18 pages)
We show how the structural and group-theoretic ideas combine in a polynomial-time algorithm to test whether graphs from proper minor-closed classes are isomorphic.
- Sublinear Separators (8 pages)