2026-08-19T15:35:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6782 2024-03-06T10:38:52Z ddc:004 open_access

Packing Short Plane Spanning Trees in Complete Geometric Graphs Aichholzer, Oswin Hackl, Thomas Korman, Matias Pilz, Alexander Rote, Günter van Renssen, André Roeloffzen, Marcel Vogtenhuber, Birgit Geometric Graphs Graph Packing Plane Graphs Minimum Spanning Tree Bottleneck Edge 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and Günter Rote and André van Renssen and Marcel Roeloffzen and Birgit Vogtenhuber 2016 Is Part Of LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2016.9 urn:nbn:de:0030-drops-67823 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.9 eng https://creativecommons.org/licenses/by/3.0/legalcode