Packing Plane Spanning Trees and Paths in Complete Geometric Graphs
share
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 Ω(√(n)). Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths).
READ FULL TEXT