License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.9
URN: urn:nbn:de:0030-drops-67823
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6782/
Go to the corresponding LIPIcs Volume Portal

Aichholzer, Oswin ; Hackl, Thomas ; Korman, Matias ; Pilz, Alexander ; Rote, Günter ; van Renssen, André ; Roeloffzen, Marcel ; Vogtenhuber, Birgit

Packing Short Plane Spanning Trees in Complete Geometric Graphs

pdf-format:
LIPIcs-ISAAC-2016-9.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{aichholzer_et_al:LIPIcs:2016:6782,
  author =	{Oswin Aichholzer and Thomas Hackl and Matias Korman and Alexander Pilz and G{\"u}nter Rote and Andr{\'e} van Renssen and Marcel Roeloffzen and Birgit Vogtenhuber},
  title =	{{Packing Short Plane Spanning Trees in Complete Geometric Graphs}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6782},
  URN =		{urn:nbn:de:0030-drops-67823},
  doi =		{10.4230/LIPIcs.ISAAC.2016.9},
  annote =	{Keywords: Geometric Graphs, Graph Packing, Plane Graphs, Minimum Spanning Tree, Bottleneck Edge}
}

Keywords: Geometric Graphs, Graph Packing, Plane Graphs, Minimum Spanning Tree, Bottleneck Edge
Collection: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue Date: 2016
Date of publication: 07.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI