Projects per year
Abstract
Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted rawings. A simple drawing is generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the rawing at most once and there is a ray emanating from O which crosses every edge exactly once.
Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n1/2) pairwise disjoint edges and a plane path of length Ω(log n / log log n). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.
Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n1/2) pairwise disjoint edges and a plane path of length Ω(log n / log log n). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.
Original language | English |
---|---|
Title of host publication | 38th International Symposium on Computational Geometry (SoCG 2022) |
Pages | 5:1--5:18 |
Number of pages | 18 |
Publication status | Published - 2022 |
Event | 38th International Symposium on Computational Geometry: SoCG 2022 - Berlin, Germany, Berlin, Germany Duration: 7 Jun 2022 → 10 Jun 2022 https://www.inf.fu-berlin.de/inst/ag-ti/socg22/socg.html |
Conference
Conference | 38th International Symposium on Computational Geometry |
---|---|
Abbreviated title | SoCG 2022 |
Country/Territory | Germany |
City | Berlin |
Period | 7/06/22 → 10/06/22 |
Internet address |
Fields of Expertise
- Information, Communication & Computing
Fingerprint
Dive into the research topics of 'Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs'. Together they form a unique fingerprint.-
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
- 1 Talk at conference or symposium
-
Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs
Alexandra Weinberger (Speaker)
Jun 2022Activity: Talk or presentation › Talk at conference or symposium › Science to science