Packing Short Plane Spanning Trees in Complete Geometric Graphs
OPEN ACCESS
Loading...
Author / Producer
Date
2016
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
27th International Symposium on Algorithms and Computation (ISAAC 2016)
Volume
64
Pages / Article No.
9
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
27th International Symposium on Algorithms and Computation (ISAAC 2016)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Geometric Graphs; Graph Packing; Plane Graphs; Minimum Spanning Tree; Bottleneck Edge
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)