Bose, Prosenjit
Spanning Properties of Variants of the Delaunay Graph (Invited Talk)
Abstract
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 tspanner 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.
BibTeX  Entry
@InProceedings{bose:LIPIcs.ISAAC.2021.2,
author = {Bose, Prosenjit},
title = {{Spanning Properties of Variants of the Delaunay Graph}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {2:12:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15435},
URN = {urn:nbn:de:0030drops154352},
doi = {10.4230/LIPIcs.ISAAC.2021.2},
annote = {Keywords: Delaunay Graph, Geometric Graph, Graph Spanner}
}
30.11.2021
Keywords: 

Delaunay Graph, Geometric Graph, Graph Spanner 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 