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