Tree decomposition for planar graphs First asked on math.SE with no replies.


Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition?
What is the optimal tree decomposition of a $d$-by-$d$ square grid? Not completely sure how to define "optimal", but it should distinguish between decomposition with one large bag and decomposition with many large bags.
For the first question, it is open whether finding a tree decomposition for planar graphs can be done in polynomial time. The best approximation algorithm may be the RatCatcher algorithm by Seymour and Thomas, which computes the branchwidth of the planar graph, so it has a 1.5 approximation ratio by the relation between branchwidth and treewidth.

For the second one, we have the following theorem about the treewidth of $k \times k$ grids:


  Theorem. A $k \times k$ grid has treewidth $k$.


And the bags can be taken with size $k+1$, with a total $k(k-1)$ bags. I'm not sure if this is what you want, so feel free to do it if you modify the definition of "optimal".