Plane Hamiltonian Cycles in Convex Drawings

A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph Kn admits a plane Hamiltonian cycle. It turned out that already the existence of much simpler non-crossing substructures in such drawings is hard to prove. Recent progress was made by Aichholzer et al. and by Suk and Zeng who proved the existence of a plane path of length Ω(log n/log log n) and of a plane matching of size Ω(n¹/²) in every simple drawing of Kn. Instead of studying simpler substructures, we prove Rafla’s conjecture for the subclass of convex drawings, the most general class in the convexity hierarchy introduced by Arroyo et al. Moreover, we show that every convex drawing of Kn contains a plane Hamiltonian path between each pair of vertices (Hamiltonian connectivity) and a plane k-cycle for each 3 ≤ k ≤ n (pancyclicity), and present further results on maximal plane subdrawings.