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

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

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.

  • 4
    $\begingroup$ In fact the duals of cubic 3-connected graphs are exactly the maximal planar graphs. $\endgroup$ – David Eppstein Aug 27 '18 at 5:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.