A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs

AbstractThis paper describes a linear time algorithm to find a Hamiltonian cycle in an arbitrary 4-connected maximal planar graph. The algorithm is based on our simplified version of Whitney's proof of his theorem: every 4-connected maximal planar graph has a Hamiltonian cycle