Spanning trees with O(1) average stretch factor

Michiel Smid
School of Computer Science, Carleton University

Let G be a connected graph in which each edge has a weight, and let T be a spanning tree of G. The stretch of two vertices p and q is the ratio of the the distance between p and q in T and the distance between p and q in G. In SODA 2007, Abraham, Bartal and Neiman showed that a spanning tree T exists such that the average stretch (over all (n choose 2) vertex pairs) is bounded by a constant.

I will prove this result for the case when G is the complete graph on a set of points in the plane, and the edge weights represent Euclidean distances.