Packing plane spanning trees and paths in complete geometric graphs

Oswin Aichholzer; Thomas Hackl; Matias Korman; M.J. van Kreveld; Maarten Löffler; Alexander Pilz; Bettina Speckmann; Emo Welzl

doi:10.1016/j.ipl.2017.04.006

Packing plane spanning trees and paths in complete geometric graphs

Oswin Aichholzer, Thomas Hackl, Matias Korman, M.J. van Kreveld, Maarten Löffler, Alexander Pilz, Bettina Speckmann, Emo Welzl

Research output: Contribution to journal › Article › Academic › peer-review

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

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 - Aug 2017

Keywords

Combinatorial problems
Geometric graph
Spanning tree
Edge disjoint graphs

Access to Document

10.1016/j.ipl.2017.04.006

1-s2.0-S0020019017300637-mainFinal published version, 349 KBLicence: Taverne

Cite this

@article{93d6a40206c0459f9668a74cbe86513a,

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

author = "Oswin Aichholzer and Thomas Hackl and Matias Korman and {van Kreveld}, M.J. and Maarten L{\"o}ffler and Alexander Pilz and Bettina Speckmann and Emo Welzl",

year = "2017",

month = aug,

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

language = "English",

volume = "124",

pages = "35--41",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier BV",

}

TY - JOUR

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

AU - Aichholzer, Oswin

AU - Hackl, Thomas

AU - Korman, Matias

AU - van Kreveld, M.J.

AU - Löffler, Maarten

AU - Pilz, Alexander

AU - Speckmann, Bettina

AU - Welzl, Emo

PY - 2017/8

Y1 - 2017/8

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 - Geometric graph

KW - Spanning tree

KW - Edge disjoint graphs

U2 - 10.1016/j.ipl.2017.04.006

DO - 10.1016/j.ipl.2017.04.006

M3 - Article

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

Fingerprint

Cite this