Using Petal-Decompositions to Build a Low Stretch Spanning Tree

We prove that any weighted graph $G=(V,E,w)$ with n points and m edges has a spanning tree T such that ∑_,v\∈ EdT(u,v)/w(u,v)=O(mlog nloglog n). Moreover, such a tree can be found in time O(mlog nloglog n). Our result is obtained using our new petal-decomposition approach which guarantees that the radius of each cluster in the tree is at most four times the radius of the induced subgraph of the cluster in the original graph.