Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs

Abstract

It is a longstanding conjecture that every simple drawing of a complete graph on $n\ge 3$ vertices contains a crossing-free Hamiltonian cycle. We strengthen this conjecture to "there exists a crossing-free Hamiltonian path between each pair of vertices" and show that this stronger conjecture holds for several classes of simple drawings, including strongly c-monotone drawings and cylindrical drawings. As a second main contribution, we give an overview on different classes of simple drawings and investigate inclusion relations between them up to weak isomorphism.

Final version as published in the journal Computing in Geometry and Topology. (30 pages, 22 figures)