Embeddings of graph distances into trees is one of the most important techniques in algorithms. Often, applications of these embeddings require that the trees into which distances are embedded are spanning trees of the input graph. However, this requirement makes embedding much more difficult. This is largely due to the fact that embedding graph distances into hierarchical partitions of the graph is well-understood and, in turn, embedding hierarchical partitions into non-spanning trees is trivial. On the other hand, no such embedding of hierarchical partitions into spanning trees is known.

We give an algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $c$-approximate clustering in roughly $n^{1+O(1/c^2)}$ time. We obtain our result by combining a new centroid-linkage HAC algorithm with a novel fully dynamic data structure for nearest neighbor search which works under adaptive updates. We also evaluate our algorithm empirically. By leveraging a state-of-the-art nearest-neighbor search library, we obtain a fast and accurate centroid-linkage HAC algorithm. Compared to an existing state-of-the-art exact baseline, our implementation maintains the clustering quality while delivering up to a $36\times$ speedup due to performing fewer distance comparisons.