Projekte pro Jahr
Abstract
In this paper, we disprove the long-standing conjecture that any complete geometric graph on 2n vertices can be partitioned into n plane spanning trees. Our construction is based on so-called bumpy wheel sets. We fully characterize which bumpy wheels can and in particular which cannot be partitioned into plane spanning trees (or even into arbitrary plane subgraphs). Furthermore, we show a sufficient condition for generalized wheels to not admit a partition into plane spanning trees, and give a complete characterization when they admit a partition into plane spanning double stars. Finally, we initiate the study of partitions into beyond planar subgraphs, namely into k-planar and k-quasi-planar subgraphs and obtain first bounds on the number of subgraphs required in this setting.
Originalsprache | englisch |
---|---|
Titel | 38th International Symposium on Computational Geometry (SoCG 2022) |
Redakteure/-innen | Xavier Goaoc, Michael Kerber |
Erscheinungsort | Dagstuhl, Germany |
Herausgeber (Verlag) | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Seiten | 6:1-6:16 |
Band | 224 |
ISBN (elektronisch) | 9783959772273 |
DOIs | |
Publikationsstatus | Veröffentlicht - 1 Juni 2022 |
Veranstaltung | 38th International Symposium on Computational Geometry: SoCG 2022 - Berlin, Germany, Berlin, Deutschland Dauer: 7 Juni 2022 → 10 Juni 2022 https://www.inf.fu-berlin.de/inst/ag-ti/socg22/socg.html |
Publikationsreihe
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Band | 224 |
ISSN (Print) | 1868-8969 |
Konferenz
Konferenz | 38th International Symposium on Computational Geometry |
---|---|
Kurztitel | SoCG 2022 |
Land/Gebiet | Deutschland |
Ort | Berlin |
Zeitraum | 7/06/22 → 10/06/22 |
Internetadresse |
ASJC Scopus subject areas
- Software
Fields of Expertise
- Information, Communication & Computing
Fingerprint
Untersuchen Sie die Forschungsthemen von „Edge Partitions of Complete Geometric 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
- 1 Workshop, Seminar oder Kurs (Teilnahme an/Organisation von)
-
5th DACH Workshop on Arrangements and Drawings
Joachim Orthaber (Teilnehmer/-in)
16 März 2021 → 23 März 2021Aktivität: Teilnahme an / Organisation von › Workshop, Seminar oder Kurs (Teilnahme an/Organisation von)