Opening Treewidth Definitions
Treewidth Definitions
- Length
- 32 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 5: Tree decomposition definition
Treewidth measures how close a graph is to a tree: it is the minimum width of a tree decomposition, where width is the largest bag size minus one. O'Donnell states the edge and connectedness rules for bags, then shows that trees have treewidth one and -vertex cliques have treewidth . Equivalent characterizations follow: chordal graphs and triangulations via maximum clique size, perfect elimination orderings, and a helicopter cops-and-robbers game where cops win when treewidth is at most . The closing part presents large grid minors as the obstruction to small treewidth, citing Robertson and Seymour's grid minor theorem and the improved bounds of Chuzhoy and Tan (2019). Part of lecture 22b of CMU 15-750, A Theorist's Toolkit, it assumes basic graph theory.

Your comment is kept while you sign up.Sign in
Defines treewidth through tree decompositions, then matches width to cops catching a robber by helicopter.
Treewidth measures how close a graph is to a tree: it is the minimum width of a tree decomposition, where width is the largest bag size minus one. O'Donnell states the edge and connectedness rules for bags, then shows that trees have treewidth one and -vertex cliques have treewidth . Equivalent characterizations follow: chordal graphs and triangulations via maximum clique size, perfect elimination orderings, and a helicopter cops-and-robbers game where cops win when treewidth is at most . The closing part presents large grid minors as the obstruction to small treewidth, citing Robertson and Seymour's grid minor theorem and the improved bounds of Chuzhoy and Tan (2019). Part of lecture 22b of CMU 15-750, A Theorist's Toolkit, it assumes basic graph theory.
Chuzhoy and Tan 2019
This lecture
Lecture 71 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.