Standard
Edge Partitions of Complete Geometric Graphs. / Aichholzer, Oswin; Obenaus, Johannes; Orthaber, Joachim; Paul, Rosna; Schnider, Patrick; Steiner, Raphael; Taubner, Tim; Vogtenhuber, Birgit.
38th International Symposium on Computational Geometry, SoCG 2022. red. / Xavier Goaoc; Michael Kerber. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. s. 1-16 6 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 224).
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
Aichholzer, O, Obenaus, J, Orthaber, J, Paul, R, Schnider, P, Steiner, R, Taubner, T & Vogtenhuber, B 2022,
Edge Partitions of Complete Geometric Graphs. i X Goaoc & M Kerber (red),
38th International Symposium on Computational Geometry, SoCG 2022., 6, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, bind 224, s. 1-16, 38th International Symposium on Computational Geometry, SoCG 2022, Berlin, Tyskland,
07/06/2022.
https://doi.org/10.4230/LIPIcs.SoCG.2022.6APA
Aichholzer, O., Obenaus, J., Orthaber, J., Paul, R., Schnider, P., Steiner, R., Taubner, T., & Vogtenhuber, B. (2022).
Edge Partitions of Complete Geometric Graphs. I X. Goaoc, & M. Kerber (red.),
38th International Symposium on Computational Geometry, SoCG 2022 (s. 1-16). [6] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Bind 224
https://doi.org/10.4230/LIPIcs.SoCG.2022.6Vancouver
Aichholzer O, Obenaus J, Orthaber J, Paul R, Schnider P, Steiner R o.a.
Edge Partitions of Complete Geometric Graphs. I Goaoc X, Kerber M, red., 38th International Symposium on Computational Geometry, SoCG 2022. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2022. s. 1-16. 6. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 224).
https://doi.org/10.4230/LIPIcs.SoCG.2022.6Author
Aichholzer, Oswin ; Obenaus, Johannes ; Orthaber, Joachim ; Paul, Rosna ; Schnider, Patrick ; Steiner, Raphael ; Taubner, Tim ; Vogtenhuber, Birgit. / Edge Partitions of Complete Geometric Graphs. 38th International Symposium on Computational Geometry, SoCG 2022. red. / Xavier Goaoc ; Michael Kerber. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. s. 1-16 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 224).
Bibtex
@inproceedings{4d3910d3e6284fc3aa8c4c576eb500d9,
title = "Edge Partitions of Complete Geometric Graphs",
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.",
keywords = "complete geometric graph, edge partition, plane spanning tree, wheel set",
author = "Oswin Aichholzer and Johannes Obenaus and Joachim Orthaber and Rosna Paul and Patrick Schnider and Raphael Steiner and Tim Taubner and Birgit Vogtenhuber",
note = "Publisher Copyright: {\textcopyright} 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; 38th International Symposium on Computational Geometry, SoCG 2022 ; Conference date: 07-06-2022 Through 10-06-2022",
year = "2022",
doi = "10.4230/LIPIcs.SoCG.2022.6",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "1--16",
editor = "Xavier Goaoc and Michael Kerber",
booktitle = "38th International Symposium on Computational Geometry, SoCG 2022",
}
RIS
TY - GEN
T1 - Edge Partitions of Complete Geometric Graphs
AU - Aichholzer, Oswin
AU - Obenaus, Johannes
AU - Orthaber, Joachim
AU - Paul, Rosna
AU - Schnider, Patrick
AU - Steiner, Raphael
AU - Taubner, Tim
AU - Vogtenhuber, Birgit
N1 - 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
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - complete geometric graph
KW - edge partition
KW - plane spanning tree
KW - wheel set
UR - http://www.scopus.com/inward/record.url?scp=85134291791&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2022.6
DO - 10.4230/LIPIcs.SoCG.2022.6
M3 - Article in proceedings
AN - SCOPUS:85134291791
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 16
BT - 38th International Symposium on Computational Geometry, SoCG 2022
A2 - Goaoc, Xavier
A2 - Kerber, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 38th International Symposium on Computational Geometry, SoCG 2022
Y2 - 7 June 2022 through 10 June 2022
ER -
