<p>The following paper shows that the Hamiltonian cycle problem is NP-complete in <strong>maximal</strong> planar graphs:</p>

<blockquote>
  <p>A. Wigderson<br>
  The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs<br>
  Technical Report #298, Department of EECS, Princeton University, February 1982.<br>
  <a href="https://www.math.ias.edu/avi/node/820" rel="noreferrer">https://www.math.ias.edu/avi/node/820</a></p>
</blockquote>

<p>In a maximal planar graph, every face is a triangle; hence the dual of a  maximal planar graph is cubic. It is easy to see that the dual of a maximal planar graph is triply connected. </p>

<p>Therefore your problem is NP-complete.</p>

CC BY-SA 4.0
2018-08-27T05:52:05.490Z
In fact the duals of cubic 3-connected graphs are exactly the maximal planar graphs.
David Eppstein
CC BY-SA 4.0
2019-06-28T07:45:56.943Z
Your answer here and your comments on a few other questions of mine (notably this one: https://cstheory.stackexchange.com/questions/41998/is-balanced-hamiltonian-cycle-np-complete-on-maximal-plane-graphs/41999#41999 )  helped me to move a research project forward. Now that it is wrapping up I would like to acknowledge your input. I would like to respect your right to keep your identity anonymous, so I am referring to you as Gamow with a link your stackexchange profile. If you would like me to acknowledge you differently or to discuss this further, please contact me at LNAJT@math.wisc.edu.
Elle Najt
CC BY-SA 4.0
2019-06-28T10:28:57.470Z
@Lorenzo: Yes, that's fine with me. It it is enough to refer to a "discussion on stackexchange" plus html.
Gamow
CC BY-SA 4.0
2018-08-26T08:49:20.620Z
2018-08-26T08:49:20.620Z
Gamow
<p>It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: <a href="https://epubs.siam.org/doi/abs/10.1137/0205049" rel="nofollow noreferrer">https://epubs.siam.org/doi/abs/10.1137/0205049</a> </p>

<p>For a problem I'm thinking about, it would be insightful to know if the Hamiltonian cycle problem was also NP-complete on the family of plane graphs whose dual is cubic and triply connected. </p>

<p>I would be interested in any result of the following form:</p>

<p>Let $D_d = \{ G \text{ a planar graph} : G^* \text{ has max degree bounded by } d \}$. Then for some $d$, Hamiltonian cycle is NP complete on $D_d$.</p>

CC BY-SA 4.0
2018-08-26T04:33:33.147Z
The degree of a vertex of G* corresponds to the number of edges in a face of G. So a simpler way of asking your question is to ask about the Hamiltonian cycle problem in planar graphs with an upper bound on the number of edges in each face. As a separate note, reducing from grid-graph Hamiltonian cycle is probably a good idea if you want to end up with each face having a small number of edges.
Mikhail Rudoy
<cc.complexity-theory><np-complete><planar-graphs>
NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?
Elle Najt
# NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

(Asked by: username_0 on 2018-08-26)

It is well known that the Hamiltonian cycle problem is NP-complete on the family of planar, cubic and triply connected graphs: <https://epubs.siam.org/doi/abs/10.1137/0205049>

For a problem I'm thinking about, it would be insightful to know if the Hamiltonian cycle problem was also NP-complete on the family of plane graphs whose dual is cubic and triply connected.

I would be interested in any result of the following form:

Let $D\_d = \{ G \text{ a planar graph} : G^\* \text{ has max degree bounded by } d \}$. Then for some $d$, Hamiltonian cycle is NP complete on $D\_d$.

**Tags:** cc.complexity-theory, np-complete, planar-graphs

> **Comments:**
> **username_1**: The degree of a vertex of G* corresponds to the number of edges in a face of G. So a simpler way of asking your question is to ask about the Hamiltonian cycle problem in planar graphs with an upper bound on the number of edges in each face. As a separate note, reducing from grid-graph Hamiltonian cycle is probably a good idea if you want to end up with each face having a small number of edges.  

---

## 1 answers

### Answer by username_2 on 2018-08-26. Score: 8 | Accepted answer

The following paper shows that the Hamiltonian cycle problem is NP-complete in **maximal** planar graphs:

> A. Wigderson  
> The Complexity of the Hamiltonian Circuit Problem for Maximal Planar Graphs  
> Technical Report #298, Department of EECS, Princeton University, February 1982.  
> <https://www.math.ias.edu/avi/node/820>

In a maximal planar graph, every face is a triangle; hence the dual of a maximal planar graph is cubic. It is easy to see that the dual of a maximal planar graph is triply connected.

Therefore your problem is NP-complete.

> **Comments:**
> **username_3**: In fact the duals of cubic 3-connected graphs are exactly the maximal planar graphs.  
> **username_0**: Your answer here and your comments on a few other questions of mine (notably this one: https://cstheory.stackexchange.com/questions/41998/is-balanced-hamiltonian-cycle-np-complete-on-maximal-plane-graphs/41999#41999 )  helped me to move a research project forward. Now that it is wrapping up I would like to acknowledge your input. I would like to respect your right to keep your identity anonymous, so I am referring to you as username_2 with a link your stackexchange profile. If you would like me to acknowledge you differently or to discuss this further, please contact me at LNAJT@math.wisc.edu.  
> **username_2**: @Lorenzo: Yes, that's fine with me. It it is enough to refer to a "discussion on stackexchange" plus html.  

---

