Packing plane spanning trees and paths in complete geometric graphs
Publication date
2017-08
Authors
Aichholzer, Oswin
Hackl, Thomas
Korman, Matias
van Kreveld, M.J.
Löffler, Maarten
Pilz, Alexander
Speckmann, Bettina
Welzl, Emo
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
No license information available
Abstract
We consider the following question: How many edge-disjoint plane spanning trees are contained in a complete geometric graph GKn on any set S of n points in general position in the plane? We show that this number is in Ω(n). Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths).
Keywords
Combinatorial problems, Geometric graph, Spanning tree, Edge disjoint graphs, Taverne
Citation
Aichholzer, O, Hackl, T, Korman, M, van Kreveld, M J, Löffler, M, Pilz, A, Speckmann, B & Welzl, E 2017, 'Packing plane spanning trees and paths in complete geometric graphs', Information Processing Letters, vol. 124, pp. 35-41. https://doi.org/10.1016/j.ipl.2017.04.006