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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000559975Publication status
publishedExternal links
Book title
38th International Symposium on Computational GeometryJournal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
edge partition; complete geometric graph; plane spanning tree; wheel setOrganisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
03672 - Steger, Angelika / Steger, Angelika
More
Show all metadata