Packing Plane Spanning Trees and Paths in Complete Geometric Graphs
Oswin Aichholzer, Thomas Hackl, Matias Korman, Marc J. van Kreveld, Maarten Löffler, Alexander Pilz, Bettina Speckmann, Emo Welzl · TU/e Research Portal · 2017
We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph $GK_n$ on any set $S$ of $n$ points in general position in the plane? We show that this number is in $Ω(\sqrt{n})$. Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths).