<p>Planar separators easily give an $n^{O(\sqrt{n})}$ algorithm. This can be <a href="http://www.sciencedirect.com/science/article/pii/S0167637705000763">improved</a> to $2^{O(\sqrt{n})}$ which is optimal (up to the constant in the exponent) for general planar graphs assuming ETH. I am not sure if being cubic helps or not. </p>

CC BY-SA 3.0
2014-09-06T11:53:20.997Z
I found that the treewidth problem on cubic planar graphs is an open problem according to graph classes database. So, it may be possible to get faster algorithms for cubic planar graphs.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-09-07T15:12:01.930Z
I think by "open" the graph classes database usually means it's open whether a polytime algorithm exists. Not that it's open to prove some bound or other.
Sasho Nikolov
CC BY-SA 3.0
2014-09-05T15:48:44.133Z
2014-09-05T15:48:44.133Z
Sasho Nikolov
<p>Actually, you don't need to exploit the "Catalan structure" in planar graphs to get a $2^{O(\sqrt{n})}$ time bound as Saeed suggests. <a href="http://arxiv.org/abs/1103.0534" rel="nofollow">Cygan et al.</a> show you how to detect a Hamiltonian Cycle in $\operatorname{poly}(n)4^{\operatorname{tw}(G)}$ time even in general graphs, and in the final version of the paper they also describe how this can be improved to $\operatorname{poly}(n)3^{\operatorname{tw}(G)}$ time in cubic graphs. </p>

<p>The above algorithm is randomized. If you insist on a deterministic one, this is also possible with a slightly larger base constant, see <a href="http://arxiv.org/abs/1211.1505" rel="nofollow">Bodlaender et al.</a></p>

CC BY-SA 3.0
2014-09-06T11:31:55.390Z
I think the paper you mentioned is based on isolation lemma, it's also a nice idea but it's randomized algorithm. BTW bw < 1.5 tw < 3l were l is a min{diameter in G, diameter in dual of G} so in planar graph l belongs to O (\sqrt {n}).
Saeed
CC BY-SA 3.0
2014-09-06T11:37:44.917Z
Is it an open problem to improve the treewidth bound on cubic planar graphs to $tw=o(\sqrt{n})$?
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-09-06T13:02:34.720Z
@MohammadAl-Turkistany, Wall is planar and almost cubic graph and its treewidth (and its dual tw) is $\theta(\sqrt{n})$. (P.S: just adding edge between some of vertices in its outer face makes it cubic, but does not decrease the treewidth and does not effect planarity).
Saeed
CC BY-SA 3.0
2014-09-07T17:26:16.170Z
+1 Thank you for your answer. I wish that I was able to accept more than one answer.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-09-06T06:57:32.040Z
2014-09-07T07:04:41.603Z
2014-09-07T07:04:41.603Z
Andreas Björklund
<p>As mentioned, different methods such as branch decomposition (or tree decomposition) give subexponential algorithm which can improve simply by Catalan structure in planar graph to $2^{O(\sqrt{n})}$. Furthermore we can extend those results to graphs of bounded genus, that means even in graphs of bounded genus (and even on excluded minors) the problem is subexponential time solvable as described in <a href="http://arxiv.org/abs/1104.2486" rel="nofollow">Dynamic Programming for Graphs on surfaces</a>.</p>

CC BY-SA 3.0
2014-09-05T16:09:00.970Z
2014-09-07T10:59:11.910Z
2014-09-07T10:59:11.910Z
Saeed
<p>There are several graph $NP$-complete problems that have sub-exponential time algorithm on planar graph instances. </p>

<p>What is the fastest algorithm for HC problem on cubic planar graphs? Is there a sub-exponential algorithm for this class of graphs?</p>

<ds.algorithms><graph-theory>
Sub-exponential algorithm for Hamiltonian cycle problem on cubic planar graphs?
Mohammad Al-Turkistany
# Sub-exponential algorithm for Hamiltonian cycle problem on cubic planar graphs?

(Asked by: username_0 on 2014-09-05)

There are several graph $NP$-complete problems that have sub-exponential time algorithm on planar graph instances.

What is the fastest algorithm for HC problem on cubic planar graphs? Is there a sub-exponential algorithm for this class of graphs?

**Tags:** ds.algorithms, graph-theory


---

## 3 answers

### Answer by username_1 on 2014-09-05. Score: 7 | Accepted answer

Planar separators easily give an $n^{O(\sqrt{n})}$ algorithm. This can be [improved](http://www.sciencedirect.com/science/article/pii/S0167637705000763) to $2^{O(\sqrt{n})}$ which is optimal (up to the constant in the exponent) for general planar graphs assuming ETH. I am not sure if being cubic helps or not.

> **Comments:**
> **username_0**: I found that the treewidth problem on cubic planar graphs is an open problem according to graph classes database. So, it may be possible to get faster algorithms for cubic planar graphs.  
> **username_1**: I think by "open" the graph classes database usually means it's open whether a polytime algorithm exists. Not that it's open to prove some bound or other.  

---

### Answer by username_2 on 2014-09-06. Score: 8

Actually, you don't need to exploit the "Catalan structure" in planar graphs to get a $2^{O(\sqrt{n})}$ time bound as username_3 suggests. [Cygan et al.](http://arxiv.org/abs/1103.0534) show you how to detect a Hamiltonian Cycle in $\operatorname{poly}(n)4^{\operatorname{tw}(G)}$ time even in general graphs, and in the final version of the paper they also describe how this can be improved to $\operatorname{poly}(n)3^{\operatorname{tw}(G)}$ time in cubic graphs.

The above algorithm is randomized. If you insist on a deterministic one, this is also possible with a slightly larger base constant, see [Bodlaender et al.](http://arxiv.org/abs/1211.1505)

> **Comments:**
> **username_3**: I think the paper you mentioned is based on isolation lemma, it's also a nice idea but it's randomized algorithm. BTW bw < 1.5 tw < 3l were l is a min{diameter in G, diameter in dual of G} so in planar graph l belongs to O (\sqrt {n}).  
> **username_0**: Is it an open problem to improve the treewidth bound on cubic planar graphs to $tw=o(\sqrt{n})$?  
> **username_3**: @MohammadAl-Turkistany, Wall is planar and almost cubic graph and its treewidth (and its dual tw) is $\theta(\sqrt{n})$. (P.S: just adding edge between some of vertices in its outer face makes it cubic, but does not decrease the treewidth and does not effect planarity).  
> **username_0**: +1 Thank you for your answer. I wish that I was able to accept more than one answer.  

---

### Answer by username_3 on 2014-09-05. Score: 6

As mentioned, different methods such as branch decomposition (or tree decomposition) give subexponential algorithm which can improve simply by Catalan structure in planar graph to $2^{O(\sqrt{n})}$. Furthermore we can extend those results to graphs of bounded genus, that means even in graphs of bounded genus (and even on excluded minors) the problem is subexponential time solvable as described in [Dynamic Programming for Graphs on surfaces](http://arxiv.org/abs/1104.2486).


---

