Plane paths in simple drawings of complete graphs

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

Publikation: KonferenzbeitragAbstractBegutachtung

Abstract

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) )$.
Originalspracheenglisch
Seiten4-4
Seitenumfang1
PublikationsstatusVeröffentlicht - 2021
VeranstaltungXIX Spanish Meeting on Computational Geometry: EGC21 - Virtual- Madrid, Spain, Virtuell, Spanien
Dauer: 5 Juli 20217 Juli 2021
https://quantum-explore.com/egc21/
https://quantum-explore.com/egc21-program/

Konferenz

KonferenzXIX Spanish Meeting on Computational Geometry
KurztitelEGC21
Land/GebietSpanien
OrtVirtuell
Zeitraum5/07/217/07/21
Internetadresse

Fields of Expertise

  • Information, Communication & Computing

Fingerprint

Untersuchen Sie die Forschungsthemen von „Plane paths in simple drawings of complete graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren