Graph Minors:Proofs and Algorithms

The Graph Minors project developed by Robertson and Seymour towards proving Wagner's Conjecture, despite its deep combinatorial nature, has been characterised as one the most influential results in algorithmic graph theory. In this tutorial, we describe the basic combinatorial ideas of the proof and the main algorithmic techniques that emerged by this project. We also present some of the the most challenging open problems in this area.


Part 1. Wagner's Conjecture and the Graph Minors series

1.1. Graph Minors and W.Q.O.
1.2. Relations on Graphs
1.3. Wagner's Conjecture
1.4. Kruskal's Theorem
1.5. Branch decompositions
1.6. The grid-minor-excluding theorem
1.7. Wagner's conjecture for planar graphs

Part 2. Algorithmic consequences of the R&S theorem

2.1. Graph parameters
2.2. Parameterized complexity
2.3. Parameters, Classes and Obstructions
2.4. Meta-algorithms from Graph Minors
2.5. Applications

Part 3. Bidimensionality for minors and contractions

3.1. Win/Win approach
3.2 Minor Bidimensionality
3.3 Contraction-Bidimensionality
3.4 Limits of bidimensionality

Part 4. The irrelevant vertex technique

4.1. The k-disjoint paths problem
4.2. Walls and their subdivisions
4.3. Irrelevant vertices
4.4. More problems
4.5 Open problems

-----------------------------------------------------------------------------------------------------

Supported by the MCINN program "ayudas de movilidad de profesores en másters oficiales"