TY - JOUR
AU - Aichholzer, Oswin
AU - Orthaber, Joachim
AU - Vogtenhuber, Birgit
PY - 2024/01/24
Y2 - 2024/11/07
TI - Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs
JF - Computing in Geometry and Topology
JA - CompGeomTop
VL - 3
IS - 2
SE - Original Research Articles
DO - 10.57717/cgt.v3i2.47
UR - https://cgt-journal.org/index.php/cgt/article/view/47
SP - 5:1-5:30
AB - <p style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;">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.</p>
ER -