Tree decomposition for planar graphs

Question

First asked on math.SE with no replies.

1. Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition?
2. 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.

Answer 1

If what you really want is a good elimination order, you might be looking for generalized nested dissection. This is the strategy that exploits the good separators of a planar graph to give $O(n^{\omega/2})$ algorithms for Gaussian elimination, determinant, etc. for matrices coming from planar graphs.

Answer 2

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".

Answer 3

If you don't want an optimal tree decomposition, you can build a tree decomposition by computing separators recursively.