The Planar Hamiltonian Circuit Problem is NP-Complete
Michael R. Garey, D. S. Johnson, Robert Endre Tarjan · SIAM Journal on Computing · 1976
We consider the problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit. We show that this problem is NP-complete. Hence the Hamiltonian circuit problem for this class of graphs, or any larger class containing all such graphs, is probably computationally intractable.