# NP completeness of Hamiltonian cycle for the family of *dual graphs* to plane, cubic, triply connected graphs?

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

• 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. Aug 26 '18 at 4:33

## 1 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.

• In fact the duals of cubic 3-connected graphs are exactly the maximal planar graphs. Aug 27 '18 at 5:52
• Your answer here and your comments on a few other questions of mine (notably this one: cstheory.stackexchange.com/questions/41998/… ) 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. Jun 28 '19 at 7:45
• @Lorenzo: Yes, that's fine with me. It it is enough to refer to a "discussion on stackexchange" plus html. Jun 28 '19 at 10:28