Tree decomposition of graphs with low height

Question

Fix a parameter D and let the $D$-treewidth be the minimum width among tree-decompositions of H where the underlying tree has height D.

We know:

• 1-tw $= |V(H)|$.
• 2-tw $\leq vc(H)$, but this is not tight, as the matching has small 2-tw. Here $vc(H)$ is vertex cover number.
• b-tw $\leq 4 \cdot tw(H) + 3$ for $b \geq O(log |V(H)|)$, by this paper: https://research-explorer.ista.ac.at/download/5427/5471/IST-2014-314-v1%2B1_long.pdf

Can we say something in general about D-treewidth? In particular, how does $D$-treewidth decrease as we increase $D$.

Answer 1

One way to address this question is to think of a tree decomposition as an unrooted tree. Then, it is easy to see that its diameter is related to the depth by a factor of 2. Searching for diameter, instead of depth, may help you find more related results.

In this paper by Bodlaender and Hagerup, for example, they do something which sounds like the inverse function of what you want: they determine some pretty good bounds on the minimum diameter necessary in a decomposition of a graph of treewidth $k$, if you allow bags to have width $K > k$.