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

Improve this question
$\endgroup$
1
  • 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
    Commented Aug 26, 2018 at 4:33

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ In fact the duals of cubic 3-connected graphs are exactly the maximal planar graphs. $\endgroup$
    – David Eppstein
    Commented Aug 27, 2018 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 [email protected]. $\endgroup$
    – Elle Najt
    Commented Jun 28, 2019 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
    Commented Jun 28, 2019 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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