Georgia Institute of Technology College of Sciences

The graph minor structure theorem of Robertson and Seymour gives anapproximate characterization of which graphs do not contain some fixedgraph H as a minor. The theorem has found numerous applications,including Robertson and Seymour's proof of the polynomial timealgorithm for the disjoint paths problem as well as the proof ofWagner's conjecture that graphs are well quasi-ordered under the minorrelation. Unfortunately, the proof of the structure theorem isextremely long and technical. We will discuss a new proof whichgreatly simplifies the argument and makes the result more widelyaccessible. This is joint work with Ken-ichi Kawarabayashi.