<p>For the first question, it is <em>open</em> whether finding a tree decomposition for planar graphs can be done in polynomial time. The best approximation algorithm may be the <a href="http://www.springerlink.com/content/q6vh7756761j1m70/"><strong>RatCatcher</strong></a> algorithm by Seymour and Thomas, which computes the <em>branchwidth</em> of the planar graph, so it has a 1.5 approximation ratio by the relation between branchwidth and treewidth.</p>

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

<blockquote>
  <p><strong>Theorem.</strong> A $k \times k$ grid has treewidth $k$.</p>
</blockquote>

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

CC BY-SA 4.0
2024-06-15T14:49:30.650Z
sorry, just for a so late follow-up, is this one still an open problem?
Edee
CC BY-SA 4.0
2024-07-13T02:32:17.717Z
As for as I know, yes.  https://cstheory.stackexchange.com/q/32505/1800
Hsien-Chih Chang 張顯之
CC BY-SA 4.0
2024-07-14T04:40:48.540Z
Thanks a lot for the reply!
Edee
CC BY-SA 2.5
2010-11-26T01:40:04.093Z
2010-11-26T01:54:17.643Z
2010-11-26T01:54:17.643Z
Hsien-Chih Chang 張顯之
<p>If you don't want an optimal tree decomposition, you can build a tree decomposition by computing separators recursively. </p>

CC BY-SA 2.5
2010-11-26T03:29:10.793Z
2010-11-26T03:29:10.793Z
Suresh Venkat
<p>If what you really want is a good elimination order, you might be looking for <a href="http://www.jstor.org/stable/2156840">generalized nested dissection</a>.  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. </p>

CC BY-SA 2.5
2010-11-27T10:16:49.587Z
Interesting, I found a whole trove of literature expanding on the method. If I understand correctly, given optimal elimination order, optimal tree decomposition is easy
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-26T14:45:37.920Z
2010-11-26T14:45:37.920Z
Jason Morton
<p>First asked on <a href="https://math.stackexchange.com/questions/10944/tree-decomposition-for-planar-nearest-neighbor-graphs">math.SE</a> with no replies.</p>

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

<ds.algorithms><graph-theory><graph-algorithms><treewidth><integer-lattice>
Tree decomposition for planar graphs
Yaroslav Bulatov
# Tree decomposition for planar graphs

(Asked by: username_0 on 2010-11-25)

First asked on [math.SE](https://math.stackexchange.com/questions/10944/tree-decomposition-for-planar-nearest-neighbor-graphs) 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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, treewidth, integer-lattice

---

## 3 answers

### Answer by username_4 on 2010-11-26. Score: 11 | Accepted answer

If what you really want is a good elimination order, you might be looking for [generalized nested dissection](http://www.jstor.org/stable/2156840). 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.

> **Comments:**
> **username_0**: Interesting, I found a whole trove of literature expanding on the method. If I understand correctly, given optimal elimination order, optimal tree decomposition is easy  

---

### Answer by username_1 on 2010-11-26. Score: 14

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**](http://www.springerlink.com/content/q6vh7756761j1m70/) 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".

> **Comments:**
> **username_2**: sorry, just for a so late follow-up, is this one still an open problem?  
> **username_1**: As for as I know, yes.  https://cstheory.stackexchange.com/q/32505/1800  
> **username_2**: Thanks a lot for the reply!  

---

### Answer by username_3 on 2010-11-26. Score: 4

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


---

