Approximating the stretch factor of Euclidean graphs

There are several results available in the literature dealing with efficien t construction of t-spanners for a given set S of n points in R-d. t-spanne rs are Euclidean graphs in which distances between vertices in G are at mos t t times the Euclidean distances between them; in other words, distances i n G are stretched by a factor of at most t. We consider the interesting dua l problem: given a Euclidean graph G whose vertex set corresponds to the se t S, compute the stretch factor of G, i.e., the maximum ratio between dista nces in G and the corresponding Euclidean distances. It can trivially be so lved by solving the all-pairs-shortest-path problem. However, if an approxi mation to the stretch factor is sufficient, then we show it can be efficien tly computed by making only O(n) approximate shortest path queries in the g raph G. We apply this surprising result to obtain efficient algorithms for approximating the stretch factor of Euclidean graphs such as paths, cycles, trees, planar graphs, and general graphs. The main idea behind the algorit hm is to use Callahan and Kosaraju's well-separated pair decomposition.