Packing Short Plane Spanning Trees in Complete Geometric Graphs

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



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.9.pdf
  • Filesize: 0.55 MB
  • 12 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/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.
Keywords
  • Geometric Graphs
  • Graph Packing
  • Plane Graphs
  • Minimum Spanning Tree
  • Bottleneck Edge

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. O. Aichholzer, T. Hackl, M. Korman, M. J. van Kreveld, M. Löffler, A. Pilz, B. Speckmann, and E. Welzl. Packing plane spanning trees and paths in complete geometric graphs. In Proc. Canadian Conference on Computational Geometry (CCCG), pages 233-238, 2014. Google Scholar
  2. P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks, 7(6):609-616, 2001. Google Scholar
  3. D. Dor and M. Tarsi. Graph decomposition is NP-complete: A complete proof of Holyer’s conjecture. SIAM Journal on Computing, 26(4):1166-1187, 1997. Google Scholar
  4. M. Fussen, R. Wattenhofer, and A. Zollinger. Interference arises at the receiver. In Proc. International Conference on Wireless Networks, Communications, and Mobile Computing (WIRELESSCOM), pages 427-432, 2005. Google Scholar
  5. A. García. Personal Communication, 2015. Google Scholar
  6. M. Korman. Minimizing interference in ad-hoc networks with bounded communication radius. Information Processing Letters, 112(19):748-752, 2012. Google Scholar
  7. E. Kranakis, H. Singh, and J. Urrutia. Compass routing on geometric networks. In Proc. Canadian Conference on Computational Geometry (CCCG), pages 51-54, 1999. Google Scholar
  8. M. Priesler and M. Tarsi. Multigraph decomposition into stars and into multistars. Discrete Mathematics, 296(2-3):235-244, 2005. Google Scholar
  9. M. Tarsi. Decomposition of a complete multigraph into simple paths: Nonbalanced handcuffed designs. Journal of Combinatorial Theory, Series A, 34(1):60-70, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail