Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs

Oswin Aichholzer; Joachim Orthaber; Birgit Vogtenhuber

Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 39th European Workshop on Computational Geometry (EuroCG 2023)
Pages	33:1-33:7
Publication status	Published - 2023
Event	39th European Workshop on Computational Geometry: EuroCG 2023 - Barcelona, Spain Duration: 29 Mar 2023 → 31 Mar 2023 https://dccg.upc.edu/eurocg23/

Conference

Conference	39th European Workshop on Computational Geometry
Country/Territory	Spain
City	Barcelona
Period	29/03/23 → 31/03/23
Internet address	https://dccg.upc.edu/eurocg23/

Fields of Expertise

Information, Communication & Computing

Access to Document

https://dccg.upc.edu/eurocg23/wp-content/uploads/2023/03/Session-5B-Talk-2.pdf

1 Conference or symposium (Participation in/Organisation of)
1 Talk at conference or symposium

39th European Workshop on Computational Geometry
Orthaber, J. R. (Participant)
29 Mar 2023 → 31 Mar 2023
Activity: Participation in or organisation of › Conference or symposium (Participation in/Organisation of)
Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs
Orthaber, J. R. (Speaker)
30 Mar 2023
Activity: Talk or presentation › Talk at conference or symposium › Science to science

1 Master's Thesis

Crossing-Free Hamiltonian Cycles in Simple Drawings of the Complete Graph: (And What We Found Along the Way)
Orthaber, J., Jun 2022, 96 p.
Research output: Thesis › Master's Thesis

Open Access

Cite this

Aichholzer, O, Orthaber, J & Vogtenhuber, B 2023, Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs. in Proceedings of the 39th European Workshop on Computational Geometry (EuroCG 2023). pp. 33:1-33:7, 39th European Workshop on Computational Geometry, Barcelona, Spain, 29/03/23. <https://dccg.upc.edu/eurocg23/wp-content/uploads/2023/03/Session-5B-Talk-2.pdf>

@inproceedings{ef9efeb2f2024c04bfb38e85b4a0bf73,

title = "Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs",

abstract = "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.",

author = "Oswin Aichholzer and Joachim Orthaber and Birgit Vogtenhuber",

year = "2023",

language = "English",

pages = "33:1--33:7",

booktitle = "Proceedings of the 39th European Workshop on Computational Geometry (EuroCG 2023)",

note = "39th European Workshop on Computational Geometry : EuroCG 2023 ; Conference date: 29-03-2023 Through 31-03-2023",

url = "https://dccg.upc.edu/eurocg23/",

}

TY - GEN

T1 - Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs

AU - Aichholzer, Oswin

AU - Orthaber, Joachim

AU - Vogtenhuber, Birgit

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

M3 - Conference paper

SP - 33:1-33:7

BT - Proceedings of the 39th European Workshop on Computational Geometry (EuroCG 2023)

T2 - 39th European Workshop on Computational Geometry

Y2 - 29 March 2023 through 31 March 2023

ER -

Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs

Abstract

Conference

Fields of Expertise

Access to Document

Activities

39th European Workshop on Computational Geometry

Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs

Research output

Crossing-Free Hamiltonian Cycles in Simple Drawings of the Complete Graph: (And What We Found Along the Way)

Cite this