Georgia Institute of Technology College of Sciences

The Weak Structure Theorem of Robertson and Seymour is the cornerstone of many of the algorithmic applications of graph minors techniques. The theorem states that any graph which has both large tree-width and excludes a fixed size clique minor contains a large, nearly planar subgraph. In this talk, we will discuss a new proof of this result which is significantly simpler than the original proof of Robertson and Seymour. As a testament to the simplicity of the proof, one can extract explicit constants to the bounds given in the theorem. We will assume no previous knowledge about graph minors or tree-width. This is joint work with Ken Kawarabayashi and Robin Thomas