Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with excluded minors make heavy use of Robertson and Seymour’s structure theory for graphs with excluded minors, especially when the treewidth is large (small treewidth usually makes problem to be easily solved by dynamic programming) [2].
However, there are some results are trying to avoid using the grid minor theorem. For example, Chekuri and Chuzhoy [3] show a framework for using theorems to bypass the well-known Grid-Minor Theorem of Robertson and Seymour in some applications. In particular, this leads to substantially improved parameters in some Erdos-Posa-type results, and faster running times for algorithms for some fi xed parameter tractable problems.
Do you know any other examples of problems with large treewidth avoid using the grid minor theorem?