Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs.What is the best known upper bound on the length of longest simple path in non-Hamiltonian cubic planar bipartite graphs?Edit: Also, I am interested in non-trivial lower bounds on the length of the longest simple path in this class of graphs.
Upper bounds on the length of longest simple path in non-Hamiltonian graph?
cc.complexity theory;graph theory
There exist cubic bipartite planar graphs in which the longest path has length only $O(\log^2 n)$: