Edge Partitions of Complete Geometric Graphs
OPEN ACCESS
Loading...
Author / Producer
Date
2022
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Book title
38th International Symposium on Computational Geometry
Volume
224
Pages / Article No.
6
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
38th International Symposium on Computational Geometry (SoCG 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
edge partition; complete geometric graph; plane spanning tree; wheel set
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)