Plane paths in simple drawings of complete graphs

Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, Alexandra Weinberger

Research output: Contribution to conferenceAbstractpeer-review


Simple drawings are drawings of graphs in the plane
such that vertices are distinct points in the plane,
edges are Jordan arcs connecting their endpoints, and
edges intersect at most once either in a proper crossing
or in a shared endpoint.
It is conjectured that every simple drawing of the
complete graph with $n$ vertices, $K_n$, contains a plane
Hamiltonian cycle, and consequently a plane Hamil-
tonian path. However, to the best of our knowledge,
$\Omega((\log n)^{1/6})$ is currently the best known lower bound
for the length of a plane path contained in any simple
drawing of $K_n$. We improve this bound to $\Omega(\log n / (\log \log n) )$.
Original languageEnglish
Number of pages1
Publication statusPublished - 2021
EventXIX Spanish Meeting on Computational Geometry: EGC21 - Virtual- Madrid, Spain, Virtuell, Spain
Duration: 5 Jul 20217 Jul 2021


ConferenceXIX Spanish Meeting on Computational Geometry
Abbreviated titleEGC21
Internet address


  • Discrete and Computational Geometry

Fields of Expertise

  • Information, Communication & Computing


Dive into the research topics of 'Plane paths in simple drawings of complete graphs'. Together they form a unique fingerprint.

Cite this