2026-08-15T12:11:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16014 2024-03-06T10:56:44Z ddc:004 open_access

Edge Partitions of Complete Geometric Graphs Aichholzer, Oswin Obenaus, Johannes Orthaber, Joachim Paul, Rosna Schnider, Patrick Steiner, Raphael Taubner, Tim Vogtenhuber, Birgit edge partition complete geometric graph plane spanning tree wheel set 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oswin Aichholzer and Johannes Obenaus and Joachim Orthaber and Rosna Paul and Patrick Schnider and Raphael Steiner and Tim Taubner and Birgit Vogtenhuber 2022 Is Part Of LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2022.6 urn:nbn:de:0030-drops-160141 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.6 eng https://creativecommons.org/licenses/by/4.0/legalcode