Let G be a geometric graph whose vertex set S is a set of n points in ℝd. The stretch factor of two distinct points p and q in S is the ratio of their shortest-path distance in G and their Euclidean distance. We consider the problem of approximating the sum of all (n/2) stretch factors determined by all pairs of points in S. We show that for paths, cycles, and trees, this sum can be approximated, within a factor of 1+ε, in O(n polylog(n)) time. For plane graphs, we present a (2+ε)-approximation algorithm with running time O(n 5/3 polylog(n)), and a (4+ε)-approximation algorithm with running time O(n 3/2 polylog(n)).

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-642-17517-6_6
Citation
Cheng, S.-W. (Siu-Wing), Knauer, C. (Christian), Langerman, S. (Stefan), & Smid, M. (2010). Approximating the average stretch factor of geometric graphs. doi:10.1007/978-3-642-17517-6_6