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

The Hamiltonian cycle problem is a well-known NP-complete problem. Some restrictions of this problem, even for planar graphs, remain NP-complete while other subclasses possess polynomial-time algorithms. The authors consider the class of 4-connected maximal planar graphs. Using a slight modification of Whitney's theorem [\textit{H. Whitney}, Ann. Math., II. Ser. 32, 378-390 (1931; Zbl 0002.16101)] the authors present a linear time algorithm for finding a Hamiltonian cycle in 4-connected maximal planar graphs.