2026-07-23T18:55:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19963 2024-06-06T06:21:13Z ddc:004 open_access

Plane Hamiltonian Cycles in Convex Drawings Bergold, Helena Felsner, Stefan M. Reddy, Meghana Orthaber, Joachim Scheucher, Manfred simple drawing convexity hierarchy plane pancyclicity plane Hamiltonian connectivity maximal plane subdrawing A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph K_n 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^{1/2}) in every simple drawing of K_n. 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 K_n 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Helena Bergold and Stefan Felsner and Meghana M. Reddy and Joachim Orthaber and Manfred Scheucher 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.18 urn:nbn:de:0030-drops-199630 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.18 eng https://creativecommons.org/licenses/by/4.0/legalcode