The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs

An algorithm for the determination of an Hamiltonian circuit in a 4-connected planar graph is presented. The timing for this algorithm depends on $n^3 $ (where n is the number of edges in the graph); the storage requirement also depends on $n^3 $. This paper completes the result of Garey, Johnson and Tarjan [SIAM J. Comput., 5 (1976), pp. 704–714] which claims that the problem is NP-complete for 3-connected planar graphs. This algorithm is inspired by the proof of Tutte’s theorem which implies the existence of Hamiltonian circuits in 4-connected planar graphs.