Edge Partitions of Complete Geometric Graphs

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

  • 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.

OriginalsprogEngelsk
Titel38th International Symposium on Computational Geometry, SoCG 2022
RedaktørerXavier Goaoc, Michael Kerber
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdato2022
Sider1-16
Artikelnummer6
ISBN (Elektronisk)9783959772273
DOI
StatusUdgivet - 2022
Begivenhed38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, Tyskland
Varighed: 7 jun. 202210 jun. 2022

Konference

Konference38th International Symposium on Computational Geometry, SoCG 2022
LandTyskland
ByBerlin
Periode07/06/202210/06/2022
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind224
ISSN1868-8969

Bibliografisk note

Funding Information:
Acknowledgements Research on this work has been initiated in March 2021, at the 5th research workshop of the collaborative D-A-CH project Arrangements and Drawings, which was funded by the DFG, the FWF, and the SNF. We thank the organizers and all participants for fruitful discussions. Further, we thank the anonymous reviewers for their insightful comments and suggestions.

Funding Information:
Funding Oswin Aichholzer: Partially supported by the Austrian Science Fund (FWF): W1230 and the European Union H2020-MSCA-RISE project 73499 – CONNECT. Johannes Obenaus: Supported by ERC StG 757609. Rosna Paul: Supported by the Austrian Science Fund (FWF): W1230. Patrick Schnider: Supported by ERC StG 716424 – CASe. Raphael Steiner: Supported by an ETH Zurich Postdoctoral Fellowship. Birgit Vogtenhuber: Partially supported by the Austrian Science Fund (FWF): I 3340-N35.

Funding Information:
Oswin Aichholzer: Partially supported by the Austrian Science Fund (FWF): W1230 and the European Union H2020-MSCA-RISE project 73499 - CONNECT. Johannes Obenaus: Supported by ERC StG 757609. Rosna Paul: Supported by the Austrian Science Fund (FWF): W1230. Patrick Schnider: Supported by ERC StG 716424 - CASe. Raphael Steiner: Supported by an ETH Zurich Postdoctoral Fellowship. Birgit Vogtenhuber: Partially supported by the Austrian Science Fund (FWF): I 3340-N35.

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

ID: 317817007