Oriented Spanners

Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht

Titel: Oriented Spanners

Beteiligte: Buchin, Kevin [Verfasser:in]; Gudmundsson, Joachim [Verfasser:in]; Kalb, Antonia [Verfasser:in]; Popov, Aleksandr [Verfasser:in]; Rehs, Carolin [Verfasser:in]; van Renssen, André [Verfasser:in]; Wong, Sampson [Verfasser:in]

Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023

Sprache: Englisch

DOI: https://doi.org/10.4230/LIPIcs.ESA.2023.26

Schlagwörter: oriented graph ; computational geometry ; greedy triangulation ; spanner

Entstehung:

Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.

Beschreibung: 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.

Zugangsstatus: Freier Zugang

Nur in Feld suchen:

Zuletzt gesuchte Begriffe: