Input: a 3-connected cubic planar graph
feasible solution: A simple path
measure to optimize: length of the simple path
Is there a constant approximation algorithm for this problem?
The Hamiltonian circuit problem on 3-connected cubic planar graphs is NP-Complete in this paper.
A relevant question about for cubic Hamiltonian graph shows that there is no constant approximation algorithm for longest path on cubic graphs.
I'm also interested in the version where the input is a maximal planar graph.