Given a weighted graph G=(V,E) and a real number t≥1, a t-spanner of G is a spanning subgraph G′ with the property that for every edge xy in G, there exists a path between x and y in G′ whose weight is no more than t times the weight of the edge xy. We review results and present open problems on different variants of the problem of constructing plane geometric t-spanners. Crown Copyright

Additional Metadata
Keywords Delaunay triangulations, Dilation, Plane graphs, Spanners
Persistent URL dx.doi.org/10.1016/j.comgeo.2013.04.002
Journal Computational Geometry
Citation
Bose, P, & Smid, M. (2013). On plane geometric spanners: A survey and open problems. Computational Geometry, 46(7), 818–830. doi:10.1016/j.comgeo.2013.04.002