Projects per year
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) )$.
| Original language | English |
|---|---|
| Pages | 4-4 |
| Number of pages | 1 |
| Publication status | Published - 2021 |
| Event | XIX Spanish Meeting on Computational Geometry: EGC21 - Virtual- Madrid, Spain, Virtuell, Spain Duration: 5 Jul 2021 → 7 Jul 2021 https://quantum-explore.com/egc21/ https://quantum-explore.com/egc21-program/ |
Conference
| Conference | XIX Spanish Meeting on Computational Geometry |
|---|---|
| Abbreviated title | EGC21 |
| Country/Territory | Spain |
| City | Virtuell |
| Period | 5/07/21 → 7/07/21 |
| Internet address |
Keywords
- Discrete and Computational Geometry
Fields of Expertise
- Information, Communication & Computing
Fingerprint
Dive into the research topics of 'Plane paths in simple drawings of complete graphs'. Together they form a unique fingerprint.Projects
- 1 Active
-
Doctoral Program: Discrete Mathematics
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
Project: Research project
Activities
-
XIX Spanish Meeting on Computational Geometry
Alexandra Weinberger (Participant)
5 Jul 2021 → 7 Jul 2021Activity: Participation in or organisation of › Workshop, seminar or course (Participation in/Organisation of)
-
Plane paths in simple drawings of complete graphs
Alexandra Weinberger (Speaker)
5 Jul 2021Activity: Talk or presentation › Talk at conference or symposium › Science to science