# 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. – Mikhail Rudoy Aug 26 '18 at 4:33

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.