## 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*.
*
### 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.

Last update: December 8, 2016.