Edge Partitions of Complete Geometric Graphs
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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.
Originalsprog | Engelsk |
---|---|
Titel | 38th International Symposium on Computational Geometry, SoCG 2022 |
Redaktører | Xavier Goaoc, Michael Kerber |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2022 |
Sider | 1-16 |
Artikelnummer | 6 |
ISBN (Elektronisk) | 9783959772273 |
DOI | |
Status | Udgivet - 2022 |
Begivenhed | 38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, Tyskland Varighed: 7 jun. 2022 → 10 jun. 2022 |
Konference
Konference | 38th International Symposium on Computational Geometry, SoCG 2022 |
---|---|
Land | Tyskland |
By | Berlin |
Periode | 07/06/2022 → 10/06/2022 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 224 |
ISSN | 1868-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