Abstract
It is a longstanding conjecture that every simple drawing of a complete graph on n ≥ 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.
Original language | English |
---|---|
Publisher | arXiv |
DOIs | |
Publication status | Published - 27 Mar 2023 |
Keywords
- math.CO
- cs.CG