Packing plane spanning trees and paths in complete geometric graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
178 Downloads (Pure)


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).

Original languageEnglish
Pages (from-to)35-41
Number of pages7
JournalInformation Processing Letters
Publication statusPublished - 1 Aug 2017


  • Combinatorial problems
  • Edge disjoint graphs
  • Geometric graph
  • Spanning tree


Dive into the research topics of 'Packing plane spanning trees and paths in complete geometric graphs'. Together they form a unique fingerprint.

Cite this