Packing plane spanning trees and paths in complete geometric graphs

Oswin Aichholzer; Thomas Hackl; Matias Korman; Marc 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, Marc van Kreveld, Maarten Löffler, Alexander Pilz^*, Bettina Speckmann, Emo Welzl

^*Corresponding author for this work

Institute of Software Technology (7160)

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

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

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2017.04.006

Cite this

@article{55907642e5734a15b161853a74010320,

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 = "Oswin Aichholzer and Thomas Hackl and Matias Korman and {van Kreveld}, Marc and Maarten L{\"o}ffler and Alexander Pilz and Bettina Speckmann and Emo 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, Oswin

AU - Hackl, Thomas

AU - Korman, Matias

AU - van Kreveld, Marc

AU - Löffler, Maarten

AU - Pilz, Alexander

AU - Speckmann, Bettina

AU - Welzl, Emo

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

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this