# Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?

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.

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.

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

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

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

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

• Thank you. I edited my question with a condition that I wasn't considered. – Omid Ebrahimi Dec 31 '15 at 11:34
• @OmidEbrahimi I edited, trying to give alternative proof. Believe the graphclasses proof still applies, it doesn't need low degree. – joro Dec 31 '15 at 12:46
• What is $uv$? How $(u,uv,v)$ is an edge? – Omid Ebrahimi Dec 31 '15 at 13:14
• 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? – Omid Ebrahimi Dec 31 '15 at 13:43
• 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. – Andrea M Mar 25 '16 at 15:59