3
$\begingroup$

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

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

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.

$\endgroup$
  • 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
  • $\begingroup$ 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. $\endgroup$ – Lorenzo Najt Jun 28 at 7:45
  • $\begingroup$ @Lorenzo: Yes, that's fine with me. It it is enough to refer to a "discussion on stackexchange" plus html. $\endgroup$ – Gamow Jun 28 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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