Packing short plane spanning trees in complete geometric graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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.

Original languageEnglish
Title of host publication27th International Symposium on Algorithms and Computation, ISAAC 2016), December 12-14, 2016, Sydney, Australia
EditorsSeok-Hee Hong
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages12
ISBN (Electronic)9783959770262
DOIs
Publication statusPublished - 1 Dec 2016
Externally publishedYes
Event27th International Symposium on Algorithms and Computation (ISAAC 2016) - Sydney, Australia
Duration: 12 Dec 201614 Dec 2016
Conference number: 27
http://rp-www.cs.usyd.edu.au/~visual/isaac2016/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume64
ISSN (Print)1868-8969

Conference

Conference27th International Symposium on Algorithms and Computation (ISAAC 2016)
Abbreviated titleISAAC 2016
CountryAustralia
CitySydney
Period12/12/1614/12/16
Internet address

Keywords

  • Bottleneck edge
  • Geometric graphs
  • Graph packing
  • Minimum spanning tree
  • Plane graphs

Fingerprint Dive into the research topics of 'Packing short plane spanning trees in complete geometric graphs'. Together they form a unique fingerprint.

Cite this