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

Improve this question
$\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
    Commented Sep 22, 2020 at 11:06

1 Answer 1

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank you. I edited my question with a condition that I wasn't considered. $\endgroup$
    – Omid Ebrahimi
    Commented 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
    Commented Dec 31, 2015 at 12:46
  • $\begingroup$ What is $uv$? How $(u,uv,v)$ is an edge? $\endgroup$
    – Omid Ebrahimi
    Commented 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$
    – Omid Ebrahimi
    Commented 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
    Commented Mar 25, 2016 at 15:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .