AMS :: Notices of the American Mathematical Society
The treewidth of a graph, a positive integer defined using a tree of sets of vertices, is central to graph structure theory and the parametrized complexity of algorithms. Its many areas of application include sparse numerical linear algebra, Bayesian inference, control theory, game theory, low-dimensional topology, network science, and algebraic geometry.
A common definition of treewidth involves treedecompositions, of which the following is a special case. A graph is outerplanar if it can be drawn with its vertices on the boundary of a disk and its edges as noncrossing curves in the disk. Adding artificial edges, we can augment this drawing to a triangulation, a subdivision of the disk into triangles (Fig. 1), with the following properties:
A tree-decomposition, then, consists of a tree (like the tree of triangles) whose nodes are associated with sets of graph vertices, called bags. In the outerplanar case, each bag contains the three corners of a triangle. More generally, tree-decompositions may have larger bags, but must satisfy properties (2) and (3): each graph vertex belongs to bags forming a connected subtree, and each graph edge has both endpoints in at least one bag. The width of a tree-decomposition is the size of the largest bag, minus one. The treewidth of any finite undirected graph is the smallest width of any of its tree-decompositions. The “minus one” adjustment ensures that trees have width one: root any tree arbitrarily, then use bags containing each vertex and its parent. The tree of triangles of an outerplanar graph has width two.
Treewidth has many equivalent definitions. It is the maximum clique size (minus one) in a chordal supergraph minimizing this size. It is the maximum number $k$ of cops that a robber can escape in a certain pursuit-evasion game, the maximum $k$ such that some function (called a haven) maps positions of $\le k$ cops to an unoccupied subgraph into which the robber can escape, and the maximum $k$ for which in some family of connected subgraphs, all touching each other (called a bramble), $\le k$ cops always leave an unoccupied subgraph into which the robber can escape ST93. Tree-decompositions and chordal supergraphs are in some sense dual to havens and brambles: a structure of the former type provides an upper bound on treewidth, whereas a haven or bramble provides a lower bound. Treewidth is the top element in a certain lattice of well-behaved functions from graphs to numbers Hal76. Many other graph parameters are both upper bounded and lower bounded by a function of treewidth HW17.
