Basics of Treewidth

posted Jun 09 '12

Shiva Kintali
691 ● 1 ● 6 ● 22
http://www.cs.princeton.e...

updated Feb 20

Treewidth of an undirected graph $G$ measures how close $G$ is to a tree.

A tree decomposition of a graph $G(V, E)$ is a pair $\mathcal{D} = ({X_i\ |\ i \in I}, T(I, F))$ where ${X_i\ |\ i \in I}$ is a collection of subsets of $V$ (called bags) and $T(I, F)$ is a tree such that

• $\bigcup_{i \in I}{X_i} = V$.
• for all edges $(u, v) \in E$, there is an $i \in I$ with $u, v \in X_i$.
• for all $i, j, k \in I$, if $j$ is on the path from $i$ to $k$ in $T$, then $X_i \cap X_k \subseteq X_j$.

The width of a tree decomposition $\mathcal{D}$ is $\max_{i \in I}{|X_i| - 1}$. The treewidth of a graph $G$, denoted by $tw(G)$, is the minimum width over all tree decompositions of $G$.

Prove the following basic properties of treewidth :

• Treewidth of a complete graph $K_n$ is $n-1$.

• Treewidth of an $n \times n$ grid is $n$. Hence, there exist graphs of bounded-genus and unbounded treewidth.

• Treewidth of an outer-planar graph is at most two.

• A graph has no $K_4$ minor if and only if it has treewidth at most two.

• If $H$ is a minor of $G$ then treewidth of $G$ is at least that of $H$.