CS 598: Computational Topology, Fall 2009 Project Proposal - Grid Minors in Map Graphs

A key component in the proof of the Graph Minor Theorem is a Grid Minor Theorem, which states that any graph with treewidth at least some f(r) contains an r × r grid as a minor [RS]. Grid Minor Theorems find applications in designing general classes of approximation and fixed parameter tractable algorithms. The best bound for f(r) currently is 202r 5 . Robertson, Seymour, Thomas [RST] showed every planar graph with treewidth r has an Ω(r) × Ω(r) grid as a minor. Demaine and Hajiaghayi [DH] showed that every graph excluding a fixed minor, H, with treewidth r has an Ω(r)× Ω(r) grid as a minor.