[Math] Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time

computational complexitygraph theoryhamiltonian-paths

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

Best Answer

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

Related Question