> Details

Buchin, Kevin [Author]; Gudmundsson, Joachim [Author]; Kalb, Antonia [Author]; Popov, Aleksandr [Author]; Rehs, Carolin [Author]; van Renssen, André [Author]; Wong, Sampson [Author] ; Kevin Buchin and Joachim Gudmundsson and Antonia Kalb and Aleksandr Popov and Carolin Rehs and André van Renssen and Sampson Wong [Contributor]

Oriented Spanners

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: Oriented Spanners
  • Contributor: Buchin, Kevin [Author]; Gudmundsson, Joachim [Author]; Kalb, Antonia [Author]; Popov, Aleksandr [Author]; Rehs, Carolin [Author]; van Renssen, André [Author]; Wong, Sampson [Author]
  • Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.ESA.2023.26
  • Keywords: oriented graph ; computational geometry ; greedy triangulation ; spanner
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: Given a point set P in the Euclidean plane and a parameter t, we define an oriented t-spanner as an oriented subgraph of the complete bi-directed graph such that for every pair of points, the shortest cycle in G through those points is at most a factor t longer than the shortest oriented cycle in the complete bi-directed graph. We investigate the problem of computing sparse graphs with small oriented dilation. As we can show that minimising oriented dilation for a given number of edges is NP-hard in the plane, we first consider one-dimensional point sets. While obtaining a 1-spanner in this setting is straightforward, already for five points such a spanner has no plane embedding with the leftmost and rightmost point on the outer face. This leads to restricting to oriented graphs with a one-page book embedding on the one-dimensional point set. For this case we present a dynamic program to compute the graph of minimum oriented dilation that runs in 𝒪(n⁸) time for n points, and a greedy algorithm that computes a 5-spanner in 𝒪(nlog n) time. Expanding these results finally gives us a result for two-dimensional point sets: we prove that for convex point sets the greedy triangulation results in an oriented 𝒪(1)-spanner.
  • Access State: Open Access