On plane geometric spanners: A survey and open problems

摘要

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.