Roughly, a graph has small "tree-width" if it can be constructed by piecing small graphs together in a tree structure. Here we study the obstructions to the existence of such a tree structure. We find, for instance: 1. (i) a minimax formula relating tree-width with the largest such obstructions 2. (ii) an association between such obstructions and large grid minors of the graph 3. (iii) a "tree-decomposition" of the graph into pieces corresponding with the obstructions. These results will be of use in later papers.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics