On plane geometric spanners: A survey and open problems

Given a weighted graph G=(V,E)G=(V,E) and a real number t⩾1t⩾1, a t-spanner of G   is a spanning subgraph G′G′ with the property that for every edge xy in G, there exists a path between x and y   in G′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.