Spanning Tree Embeddings Are Not Much Harder than Hierarchical Partitions

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.