2012-10-03
On spanning properties of various delaunay graphs
Publication
Publication
A geometric graph G is a graph whose vertices are points in the plane and whose edges are line segments weighted by the Euclidean distance between their endpoints. In this setting, 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. Among the many beautiful properties that Delaunay graphs possess, a constant spanning ratio is one of them. We provide a comprehensive overview of various results concerning the spanning ratio among other properties of different types of Delaunay graphs and their subgraphs.
| Additional Metadata | |
|---|---|
| Keywords | Delaunay graph, Spanning ratio, Voronoi diagram |
| Persistent URL | dx.doi.org/10.1109/ISVD.2012.30 |
| Conference | 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012 |
| Citation |
Bose, P. (2012). On spanning properties of various delaunay graphs. Presented at the 2012 9th International Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2012. doi:10.1109/ISVD.2012.30
|