Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910351538257920 |
|---|---|
| author | Aichholzer, Oswin Orthaber, Joachim Vogtenhuber, Birgit |
| author_facet | Aichholzer, Oswin Orthaber, Joachim Vogtenhuber, Birgit |
| contents | It is a longstanding conjecture that every simple drawing of a complete graph on $n \geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_15610 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs Aichholzer, Oswin Orthaber, Joachim Vogtenhuber, Birgit Combinatorics Computational Geometry It is a longstanding conjecture that every simple drawing of a complete graph on $n \geq 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. |
| title | Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2303.15610 |