Edge Partitions of Complete Geometric Graphs

Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber, Rosna Paul, Patrick Schnider, Raphael Steiner, Tim Taubner, Birgit Vogtenhuber

Publikation: Beitrag in Buch/Bericht/KonferenzbandBeitrag in einem KonferenzbandBegutachtung

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.

Originalspracheenglisch
Titel38th International Symposium on Computational Geometry (SoCG 2022)
Redakteure/-innenXavier Goaoc, Michael Kerber
ErscheinungsortDagstuhl, Germany
Herausgeber (Verlag)Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Seiten6:1-6:16
Band224
ISBN (elektronisch)9783959772273
DOIs
PublikationsstatusVeröffentlicht - 1 Juni 2022
Veranstaltung38th International Symposium on Computational Geometry: SoCG 2022 - Berlin, Germany, Berlin, Deutschland
Dauer: 7 Juni 202210 Juni 2022
https://www.inf.fu-berlin.de/inst/ag-ti/socg22/socg.html

Publikationsreihe

NameLeibniz International Proceedings in Informatics, LIPIcs
Band224
ISSN (Print)1868-8969

Konferenz

Konferenz38th International Symposium on Computational Geometry
KurztitelSoCG 2022
Land/GebietDeutschland
OrtBerlin
Zeitraum7/06/2210/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.

Dieses zitieren