Tree Embedding Algorithm(G(V, d)):

In computer science, when dealing with difficult problems involving graphs and their associated metrics, one technique we usually resort to is to solve the problem on a simple subcase, in particular, on tree. In this lecture, we study the Padded Decomposition of graphs and how to build their Tree metrics with O(log n) distortion. 1 Tree Metrics Definition 1 Tree Metric- A metric (V, d) is a Tree Metric if there exists a tree T = (V,ET) with edge lengths such that d(u, v) = dT (u, v). We can build tree metrics to approximate general graph metrics, with an O(log n) distortion, where n is the number of vertices in the graph, thus the following theorem: Theorem 1 Given an undirected edge weighted graph G = (V,E), there is a randomized poly-time algorithm that produces an random edge weighted tree T = (VT, ET) such that 1. V ⊆ VT; 2. dG(u, v) ≤ dT (u, v), ∀u, v