A tutorial on Algorithmic Graph Minors by Dimitrios Thilikos

(NoNA Spring School on Algorithms, Istanbul, 12-15 March, 2009)

Abstract

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 these lectures we describe the most important (meta-) algorithmic results emerged by this project. We also present the most challenging open problems in this area.