<p>As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-30891-8_12">a survey</a> by Bodlaender from 2012 called `Fixed-Parameter Tractability of Treewidth and Pathwidth' that appeared in the festschrift for Mike Fellows' 65th birthday. The problem is listed in the conclusion of the survey.</p>

CC BY-SA 3.0
2015-09-12T10:29:27.357Z
Thanks! (And thanks also to @MarzioDeBiasi for suggesting other references.) Just out of curiosity, does someone also happen to know when the problem was first posed?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-04-14T13:25:58.660Z
@a3nm: it dates back to at least 1993, since Hans Bodlaender mentioned it in his survey "A Tourist Guide through Treewidth". Surely there must be an earlier explicit mention but I haven't yet been able to find it.
Anthony Labarre
CC BY-SA 3.0
2015-09-11T22:31:10.440Z
2015-09-11T22:31:10.440Z
Bart Jansen
<p>For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its <a href="https://en.wikipedia.org/wiki/Treewidth" rel="nofollow noreferrer">treewidth</a> is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-hard. (<a href="http://comjnl.oxfordjournals.org/content/51/3/326.abstract" rel="nofollow noreferrer">Source</a>).</p>

<p>However, when the input graph is <a href="https://en.wikipedia.org/wiki/Planar_graph" rel="nofollow noreferrer">planar</a>, much less seems to be known about the complexity. The problem was apparently <a href="https://cstheory.stackexchange.com/a/3326/4795">open</a> in 2010, a claim that also appeared in <a href="http://comjnl.oxfordjournals.org/content/51/3/326.abstract" rel="nofollow noreferrer">this survey</a> in 2007 and on <a href="https://en.wikipedia.org/wiki/Branch-decomposition#Algorithms_and_complexity" rel="nofollow noreferrer">the Wikipedia page for branch decompositions</a>. Conversely, the problem is claimed NP-hard (without proof of reference) in an <a href="http://www.labri.fr/perso/courcell/SeminaireDecGraphes/HlinOumSeeGott.pdf" rel="nofollow noreferrer">earlier version</a> of the previously mentioned survey, but I assume this is an error.</p>

<p>Is it still open to determine the complexity of the problem, given $k \in \mathbb{N}$ and a planar graph $G$, of determining $G$ has treewidth $\leq k$? If it is, was this claimed in a recent paper? Are any partial results known? If it isn't, who solved it?</p>

CC BY-SA 3.0
2015-09-11T18:41:39.250Z
Interesting question, cheers for rebooting the survey. To chip in my 2 cents, I believe the original source for the linear time proof is [Bodlaender](http://dl.acm.org/citation.cfm?id=167161) but the constant factor hidden by the asymptotic complexity notation is enormous. Perhaps an interesting spin-off / extension to your question would be whether the planar restriction allows for a more practical constant factor in this context?
Fasermaler
CC BY-SA 3.0
2015-09-11T19:15:25.367Z
I think that it is a "famous and old problem", so if you don't find a paper it is probably still an open problem. Other "evidences": Lecture from course [Graph Algorithms, Applications and Implementations](http://web.eecs.utk.edu/~cphillip/cs594_spring2015_projects/treewidth.pdf) (2015), Lecture from course [Graphs & Algorithms: Advanced Topics](http://www.ti.inf.ethz.ch/ew/lehre/GA11/lec-treewidth-new.pdf) (2014),  [Encyclopedia of algorithms](https://books.google.it/books?id=i3S9_GnHZwYC&pg=PA969&lpg=PA969#v=onepage&q&f=false) (2008).
Marzio De Biasi
CC BY-SA 3.0
2015-09-12T03:16:09.147Z
Hmm. It is relatively easy to approximate within a polylog factor...
Sariel Har-Peled
CC BY-SA 3.0
2015-09-12T03:19:34.867Z
@Sariel: It can be approximated within a constant factor (3/2) by using the fact that it and branchwidth are within a constant of each other and planar branchwidth can be computed in polynomial time. Also it can be approximated within log for all graphs using Leighton–Rao; see https://kintali.wordpress.com/2010/01/28/approximating-treewidth/
David Eppstein
CC BY-SA 3.0
2015-09-12T03:59:51.587Z
@Fasermaler the first step in Bodlaender's algorithm (and previous algorithms that were FPT but not linear time) is to compute an approximate tree decomposition on which one can use dynamic programming to find the optimal decomposition. The tighter the approximation, the faster the second step. So the fact that tighter approximations to planar treewidth can be found using branchwidth seems likely to lead to better dependence on the parameter (at the expense of going back up to polynomial from linear). But I don't know of papers that analyze this carefully.
David Eppstein
CC BY-SA 3.0
2015-09-12T16:27:37.447Z
Regarding the problem of approximating treewidth. An $\alpha$-approximation for finding sparse/balanced node-separators will give an $O(\alpha)$-approximation for treewidth. Thus, in general graphs we will get $O(\sqrt{\log n})$ via ARV/Feige-Lee-Hajiaghayi and $O(1)$ in planar and proper minor-closed families. For general graphs one can get $O(\sqrt{\log k})$ where $k$ is treewidth.
Chandra Chekuri
<reference-request><graph-theory><np-hardness><open-problem><treewidth>
Is it still open to determine the complexity of computing the treewidth of planar graphs?
Antoine Amarilli 'a3nm'
# Is it still open to determine the complexity of computing the treewidth of planar graphs?

(Asked by: username_0 on 2015-09-11)

For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its [treewidth](https://en.wikipedia.org/wiki/Treewidth) is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-hard. ([Source](http://comjnl.oxfordjournals.org/content/51/3/326.abstract)).

However, when the input graph is [planar](https://en.wikipedia.org/wiki/Planar_graph), much less seems to be known about the complexity. The problem was apparently [open](https://cstheory.stackexchange.com/a/3326/4795) in 2010, a claim that also appeared in [this survey](http://comjnl.oxfordjournals.org/content/51/3/326.abstract) in 2007 and on [the Wikipedia page for branch decompositions](https://en.wikipedia.org/wiki/Branch-decomposition#Algorithms_and_complexity). Conversely, the problem is claimed NP-hard (without proof of reference) in an [earlier version](http://www.labri.fr/perso/courcell/SeminaireDecGraphes/HlinOumSeeGott.pdf) of the previously mentioned survey, but I assume this is an error.

Is it still open to determine the complexity of the problem, given $k \in \mathbb{N}$ and a planar graph $G$, of determining $G$ has treewidth $\leq k$? If it is, was this claimed in a recent paper? Are any partial results known? If it isn't, who solved it?

**Tags:** reference-request, graph-theory, np-hardness, open-problem, treewidth

> **Comments:**
> **username_1**: Interesting question, cheers for rebooting the survey. To chip in my 2 cents, I believe the original source for the linear time proof is [Bodlaender](http://dl.acm.org/citation.cfm?id=167161) but the constant factor hidden by the asymptotic complexity notation is enormous. Perhaps an interesting spin-off / extension to your question would be whether the planar restriction allows for a more practical constant factor in this context?  
> **username_2**: I think that it is a "famous and old problem", so if you don't find a paper it is probably still an open problem. Other "evidences": Lecture from course [Graph Algorithms, Applications and Implementations](http://web.eecs.utk.edu/~cphillip/cs594_spring2015_projects/treewidth.pdf) (2015), Lecture from course [Graphs & Algorithms: Advanced Topics](http://www.ti.inf.ethz.ch/ew/lehre/GA11/lec-treewidth-new.pdf) (2014),  [Encyclopedia of algorithms](https://books.google.it/books?id=i3S9_GnHZwYC&pg=PA969&lpg=PA969#v=onepage&q&f=false) (2008).  
> **username_3**: Hmm. It is relatively easy to approximate within a polylog factor...  
> **username_4**: @Sariel: It can be approximated within a constant factor (3/2) by using the fact that it and branchwidth are within a constant of each other and planar branchwidth can be computed in polynomial time. Also it can be approximated within log for all graphs using Leighton–Rao; see https://kintali.wordpress.com/2010/01/28/approximating-treewidth/  
> **username_4**: @username_1 the first step in Bodlaender's algorithm (and previous algorithms that were FPT but not linear time) is to compute an approximate tree decomposition on which one can use dynamic programming to find the optimal decomposition. The tighter the approximation, the faster the second step. So the fact that tighter approximations to planar treewidth can be found using branchwidth seems likely to lead to better dependence on the parameter (at the expense of going back up to polynomial from linear). But I don't know of papers that analyze this carefully.  
> **username_5**: Regarding the problem of approximating treewidth. An $\alpha$-approximation for finding sparse/balanced node-separators will give an $O(\alpha)$-approximation for treewidth. Thus, in general graphs we will get $O(\sqrt{\log n})$ via ARV/Feige-Lee-Hajiaghayi and $O(1)$ in planar and proper minor-closed families. For general graphs one can get $O(\sqrt{\log k})$ where $k$ is treewidth.  

---

## 1 answers

### Answer by username_6 on 2015-09-11. Score: 13 | Accepted answer

As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is [a survey](http://link.springer.com/chapter/10.1007%2F978-3-642-30891-8_12) by Bodlaender from 2012 called `Fixed-Parameter Tractability of Treewidth and Pathwidth' that appeared in the festschrift for Mike Fellows' 65th birthday. The problem is listed in the conclusion of the survey.

> **Comments:**
> **username_0**: Thanks! (And thanks also to @MarzioDeBiasi for suggesting other references.) Just out of curiosity, does someone also happen to know when the problem was first posed?  
> **username_7**: @a3nm: it dates back to at least 1993, since Hans Bodlaender mentioned it in his survey "A Tourist Guide through Treewidth". Surely there must be an earlier explicit mention but I haven't yet been able to find it.  

---

