Packing Short Plane Spanning Trees in Complete Geometric Graphs

Oswin Aichholzer; Thomas Hackl; Matias Korman; Alexander Pilz; Günter Rote; A. van Renssen; Marcel Roeloffzen; Birgit Vogtenhuber

doi:10.4230/LIPIcs.ISAAC.2016.9

Packing Short Plane Spanning Trees in Complete Geometric Graphs

Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter Rote, A. van Renssen, Marcel Roeloffzen, Birgit Vogtenhuber

Institute of Software Technology (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two trees. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. This second approach may create cycles, but maintains planarity.

Original language	English
Title of host publication	Proceedings of the 27th Internationel Symposium on Algorithms and Computation
Pages	9.1-9.12
Edition	64
DOIs	https://doi.org/10.4230/LIPIcs.ISAAC.2016.9
Publication status	Published - 2016
Event	27th International Symposium on Algorithms and Computation: ISAAC 2016 - Sydney, Australia Duration: 12 Dec 2016 → 14 Dec 2016

Conference

Conference	27th International Symposium on Algorithms and Computation
Abbreviated title	ISAAC 2016
Country/Territory	Australia
City	Sydney
Period	12/12/16 → 14/12/16

Fields of Expertise

Information, Communication & Computing

Access to Document

10.4230/LIPIcs.ISAAC.2016.9

Cite this

Aichholzer, O, Hackl, T, Korman, M, Pilz, A, Rote, G, van Renssen, A, Roeloffzen, M & Vogtenhuber, B 2016, Packing Short Plane Spanning Trees in Complete Geometric Graphs. in Proceedings of the 27th Internationel Symposium on Algorithms and Computation. 64 edn, pp. 9.1-9.12, 27th International Symposium on Algorithms and Computation, Sydney, Australia, 12/12/16. https://doi.org/10.4230/LIPIcs.ISAAC.2016.9

@inproceedings{2452ffe4c10e4e58a53e20a45fc071ad,

title = "Packing Short Plane Spanning Trees in Complete Geometric Graphs",

abstract = "Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two trees. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. This second approach may create cycles, but maintains planarity.",

author = "Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and G{\"u}nter Rote and {van Renssen}, A. and Marcel Roeloffzen and Birgit Vogtenhuber",

year = "2016",

doi = "10.4230/LIPIcs.ISAAC.2016.9",

language = "English",

isbn = "978-3-95977-026-2",

pages = "9.1--9.12",

booktitle = "Proceedings of the 27th Internationel Symposium on Algorithms and Computation",

edition = "64",

note = "27th International Symposium on Algorithms and Computation : ISAAC 2016, ISAAC 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

}

TY - GEN

T1 - Packing Short Plane Spanning Trees in Complete Geometric Graphs

AU - Aichholzer, Oswin

AU - Hackl, Thomas

AU - Korman, Matias

AU - Pilz, Alexander

AU - Rote, Günter

AU - van Renssen, A.

AU - Roeloffzen, Marcel

AU - Vogtenhuber, Birgit

PY - 2016

Y1 - 2016

N2 - Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two trees. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. This second approach may create cycles, but maintains planarity.

AB - Given a set of points in the plane, we want to establish a connection network between these points that consists of several disjoint layers. Motivated by sensor networks, we want that each layer is spanning and plane, and that no edge is very long (when compared to the minimum length needed to obtain a spanning graph). We consider two different approaches: first we show an almost optimal centralized approach to extract two trees. Then we show a constant factor approximation for a distributed model in which each point can compute its adjacencies using only local information. This second approach may create cycles, but maintains planarity.

U2 - 10.4230/LIPIcs.ISAAC.2016.9

DO - 10.4230/LIPIcs.ISAAC.2016.9

M3 - Conference paper

SN - 978-3-95977-026-2

SP - 9.1-9.12

BT - Proceedings of the 27th Internationel Symposium on Algorithms and Computation

T2 - 27th International Symposium on Algorithms and Computation

Y2 - 12 December 2016 through 14 December 2016

ER -

Packing Short Plane Spanning Trees in Complete Geometric Graphs

Abstract

Conference

Fields of Expertise

Access to Document

Fingerprint

Cite this