Edge Partitions of Complete Geometric Graphs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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

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.

Original languageEnglish
Title of host publication38th International Symposium on Computational Geometry, SoCG 2022
EditorsXavier Goaoc, Michael Kerber
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2022
Pages1-16
Article number6
ISBN (Electronic)9783959772273
DOIs
Publication statusPublished - 2022
Event38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, Germany
Duration: 7 Jun 202210 Jun 2022

Conference

Conference38th International Symposium on Computational Geometry, SoCG 2022
LandGermany
ByBerlin
Periode07/06/202210/06/2022
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume224
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber, Rosna Paul, Patrick Schnider, Raphael Steiner, Tim Taubner, and Birgit Vogtenhuber; licensed under Creative Commons License CC-BY 4.0

    Research areas

  • complete geometric graph, edge partition, plane spanning tree, wheel set

ID: 317817007