2
$\begingroup$

Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in linear time (By this Reference). The st-order of a bi-connected planar graph makes a path that covers all vertices of $G$. So can we say Hamiltonian Path can be solved in linear time in bi-connected planar graphs with $\Delta(G)>3$ $?$

Note: I said $\Delta(G)>3$, because we know the following rule (Wikipedia Reference):

Hamiltonian Path problem remain NP-complete even for undirected planar graphs of maximum degree three.

Complementary Answer:

The st-order of a 2-connected planar graph with $\Delta(G)>3$ may doesn't give a Hamiltonian Path for it. The following image is a counterexample that shows an st-order which isn't a Hamiltonian Path.

st-order

But there is an algorithm for 4-connected planar graphs that can solve Hamiltonian Path problem in linear time (The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs).

$\endgroup$
1
  • $\begingroup$ In the counterexample above, is not the following path Hamiltonian (edges numbered 1..12 from s to t): 3,1,2,9,12,11,8,7,6,5,4,10. $\endgroup$
    – axion
    Sep 22, 2020 at 11:06

1 Answer 1

5
$\begingroup$

According to graph classes this is NP-complete even on 2-connected ∩ cubic ∩ planar.

The proof reduces it to NP-hardness of Hamiltonian cycle.


Added because of the edit.

I believe the graphclasses proof still applies, but haven't checked this.

Here is alternative proof.

HP is NP-hard in $\Delta=3$ planar 2-connected. Let $G$ be graph in this class. We can artificially increase the degree to get $\Delta > 3$.

Take edge $(u,v) \in E(G)$. Delete it and add edges $(u,uv,v),(a',u),(a',uv),(a',v)$ where $a'$ is new vertex.

This preserves planarity and 2-connectivity and keeps the property of having Hamiltonian path.

It also increases $\Delta(G')=4 > 3$.

$\endgroup$
8
  • $\begingroup$ Thank you. I edited my question with a condition that I wasn't considered. $\endgroup$ Dec 31, 2015 at 11:34
  • $\begingroup$ @OmidEbrahimi I edited, trying to give alternative proof. Believe the graphclasses proof still applies, it doesn't need low degree. $\endgroup$
    – joro
    Dec 31, 2015 at 12:46
  • $\begingroup$ What is $uv$? How $(u,uv,v)$ is an edge? $\endgroup$ Dec 31, 2015 at 13:14
  • $\begingroup$ My question is a special case of 2-connected planar graphs that is not cubic and has a lower-bound on it's maximum degree. If we have a special case, it may not remain NP-Complete. I think graphclasses reference is a general proof that may not remain in this special case. Can you say why the st-order result isn't a Hamiltonian Path? $\endgroup$ Dec 31, 2015 at 13:43
  • 1
    $\begingroup$ I'd like to remark that the proof given in graphclasses about Hamiltonian Path does not seem to be correct (just consider the dodecahedron). Nevertheless, by a slight modification, we can show that Hamiltonian Path is $\mathsf{NP}$-hard even for planar cubic bipartite graphs. Note that any connected cubic bipartite graph is $2$-connected. $\endgroup$
    – Andrea M
    Mar 25, 2016 at 15:59

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.