Packing Plane Spanning Trees and Paths in Complete Geometric Graphs
| Autor: | Aichholzer, Oswin, Hackl, Thomas, Korman, Matias, van Kreveld, Marc, Löffler, Maarten, Pilz, Alexander, Speckmann, Bettina, Welzl, Emo |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.ipl.2017.04.006 |
| Popis: | 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 $\Omega(\sqrt{n})$. Further, we consider variants of this problem by bounding the diameter and the degree of the trees (in particular considering spanning paths). Comment: This work was presented at the 26th Canadian Conference on Computational Geometry (CCCG 2014), Halifax, Nova Scotia, Canada, 2014. The journal version appeared in Information Processing Letters, 124 (2017), 35--41 |
| Databáze: | arXiv |
| Externí odkaz: |
|