2026-07-24T01:08:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15435 2024-03-06T10:55:17Z ddc:004 open_access

Spanning Properties of Variants of the Delaunay Graph (Invited Talk) Bose, Prosenjit Delaunay Graph Geometric Graph Graph Spanner A weighted geometric graph G is a graph whose n vertices are points in the plane and whose m edges are line segments weighted by the Euclidean distance between their endpoints. A t-spanner of G is a connected spanning subgraph G' with the property that for every pair of vertices x, y, the shortest path from x to y in G' has weight at most t ≥ 1 times the shortest path from x to y in G. The parameter t is commonly referred to as the spanning ratio or the stretch factor. Typically, G is a graph with Ω(n²) edges. As such, the goal in this area is to construct a subgraph G' that possesses several desirable properties such as O(n) edges and spanning ratio close to 1. In addition, when planarity is one of the desired properties, variants of Delaunay graphs play a vital role in the construction of planar geometric spanners. In this talk, we will provide a comprehensive overview of various results concerning the spanning ratio, among other several other properties, of different types of Delaunay graphs and their subgraphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prosenjit Bose 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.2 urn:nbn:de:0030-drops-154352 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.2 eng https://creativecommons.org/licenses/by/4.0/legalcode