Plane Hamiltonian Cycles in Convex Drawings

2024/03/19 by Bergold, Helena, Felsner, Stefan, Reddy, Meghana M. +2 · 2 citations
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2403.12898

Abstract

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.

Cited by

• Edge-Constrained Hamiltonian Paths on a Point Set
• Characterizing and Recognizing Twistedness

Related

• Using SAT to study plane Hamiltonian substructures in simple drawings
• Separable Drawings: Extendability and Crossing-Free Hamiltonian Cycles
• On plane cycles in geometric multipartite graphs
• Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs
• Packing 1-Plane Hamiltonian Cycles in Complete Geometric Graphs