Plane Hamiltonian Cycles in Convex Drawings
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908886417539072 |
|---|---|
| author | Bergold, Helena Felsner, Stefan Reddy, Meghana M. Orthaber, Joachim Scheucher, Manfred |
| author_facet | Bergold, Helena Felsner, Stefan Reddy, Meghana M. Orthaber, Joachim Scheucher, Manfred |
| contents | 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 \leq k \leq n$ (pancyclicity), and present further results on maximal plane subdrawings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12898 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Plane Hamiltonian Cycles in Convex Drawings Bergold, Helena Felsner, Stefan Reddy, Meghana M. Orthaber, Joachim Scheucher, Manfred Computational Geometry Discrete Mathematics Combinatorics 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 \leq k \leq n$ (pancyclicity), and present further results on maximal plane subdrawings. |
| title | Plane Hamiltonian Cycles in Convex Drawings |
| topic | Computational Geometry Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2403.12898 |