Let G = (V, E) be a n-vertex connected graph with positive edge weights. A subgraph G′ is a t-spanner if for all u, v ∈ V, the distance between u and v in the subgraph is at most t times the corresponding distance in G. We design an O(n log2 n) time algorithm which, given a set V of n points in k-dimensional space, and any constant t > 1, produces a t-spanner of the complete Euclidean graph of V. This algorithm retains the spirit of a recent O(n3 log n)-time greedy algorithm which produces t-spanners with a small number of edges and a small total edge weight; we use graph clustering techniques to achieve a more efficient implementation. Our spanners have similar size and weight sparseness as those constructed by the greedy algorithm.
