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

doi:10.1016/j.ipl.2017.04.006

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 journal › Article › Academic › peer-review

12 Citations (Scopus)

290 Downloads (Pure)

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? 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 language	English
Pages (from-to)	35-41
Number of pages	7
Journal	Information Processing Letters
Volume	124
DOIs	https://doi.org/10.1016/j.ipl.2017.04.006
Publication status	Published - 1 Aug 2017

Keywords

Combinatorial problems
Edge disjoint graphs
Geometric graph
Spanning tree

Access to Document

10.1016/j.ipl.2017.04.006

authors versionFinal author version , 363 KB

Cite this

@article{42719e90f59142a4b18d85719e3398b7,

title = "Packing plane spanning trees and paths in complete geometric graphs",

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, Edge disjoint graphs, Geometric graph, Spanning tree",

author = "O. Aichholzer and T. Hackl and M. Korman and {van Kreveld}, M.J. and M. L{\"o}ffler and A. Pilz and B. Speckmann and E. Welzl",

year = "2017",

month = aug,

day = "1",

doi = "10.1016/j.ipl.2017.04.006",

language = "English",

volume = "124",

pages = "35--41",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Packing plane spanning trees and paths in complete geometric graphs

AU - Aichholzer, O.

AU - Hackl, T.

AU - Korman, M.

AU - van Kreveld, M.J.

AU - Löffler, M.

AU - Pilz, A.

AU - Speckmann, B.

AU - Welzl, E.

PY - 2017/8/1

Y1 - 2017/8/1

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

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

KW - Combinatorial problems

KW - Edge disjoint graphs

KW - Geometric graph

KW - Spanning tree

UR - http://www.scopus.com/inward/record.url?scp=85018931031&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2017.04.006

DO - 10.1016/j.ipl.2017.04.006

M3 - Article

AN - SCOPUS:85018931031

SN - 0020-0190

VL - 124

SP - 35

EP - 41

JO - Information Processing Letters

JF - Information Processing Letters

ER -

Packing plane spanning trees and paths in complete geometric graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this