Projekte pro Jahr
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) )$.
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) )$.
Originalsprache | englisch |
---|---|
Seiten | 4-4 |
Seitenumfang | 1 |
Publikationsstatus | Veröffentlicht - 2021 |
Veranstaltung | XIX Spanish Meeting on Computational Geometry: EGC21 - Virtual- Madrid, Spain, Virtuell, Spanien Dauer: 5 Juli 2021 → 7 Juli 2021 https://quantum-explore.com/egc21/ https://quantum-explore.com/egc21-program/ |
Konferenz
Konferenz | XIX Spanish Meeting on Computational Geometry |
---|---|
Kurztitel | EGC21 |
Land/Gebiet | Spanien |
Ort | Virtuell |
Zeitraum | 5/07/21 → 7/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.Projekte
- 1 Laufend
-
DK Diskrete Mathematik
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., Sava-Huss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Projekt: Forschungsprojekt
Aktivitäten
-
XIX Spanish Meeting on Computational Geometry
Alexandra Weinberger (Teilnehmer/-in)
5 Juli 2021 → 7 Juli 2021Aktivität: Teilnahme an / Organisation von › Workshop, Seminar oder Kurs (Teilnahme an/Organisation von)
-
Plane paths in simple drawings of complete graphs
Alexandra Weinberger (Redner/in)
5 Juli 2021Aktivität: Vortrag oder Präsentation › Vortrag bei Konferenz oder Fachtagung › Science to science