1. Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, Günter
Rote, André van Renssen, Marcel Roeloffzen, and Birgit Vogtenhuber:
Packing short plane spanning trees in complete geometric graphs
In: 27th International Symposium on Algorithms and Computation
(ISAAC 2016), Editor: Seok-Hee Hong. Leibniz International Proceedings
in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für
Informatik, 2016, Vol. 64, pp. 9:1–9:12.
doi:10.4230/LIPIcs.ISAAC.2016.9. →BibTeX
2. Oswin Aichholzer, Thomas Hackl, Matias Korman, Alexander Pilz, André
van Renssen, Marcel Roeloffzen, Günter Rote, and Birgit Vogtenhuber:
Packing plane spanning graphs with short edges in complete geometric
graphs
Computational Geometry, Theory and Applications 82
(2019), 1–15. doi:10.1016/j.comgeo.2019.04.001,
arXiv:1703.05863 [cs.CG].
→BibTeX
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 too long when compared to the length needed to obtain
a spanning tree.
We consider two different approaches. First we show an almost optimal
centralized approach to extract two layers. Then we consider a distributed
model in which each point can compute its adjacencies using only information
about vertices at most a predefined distance away. We obtain a constant-factor
approximation with respect to the length of the longest edge in the graphs.
In both cases the obtained layers are plane.
Last update: March 30, 2019.