Packing Plane Spanning Trees and Paths in Complete Geometric Graphs

O. Aichholzer, T. Hackl, M. Korman, M. van Kreveld, M. Löffler, A. Pilz, B. Speckmann, and E. Welzl

Abstract:

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?

Reference: O. Aichholzer, T. Hackl, M. Korman, M. van Kreveld, M. Löffler, A. Pilz, B. Speckmann, and E. Welzl. Packing plane spanning trees and paths in complete geometric graphs. Information Processing Letters (IPL), 124:35-41, 2017.