Metric Embedding via Shortest Path Decompositions

We study the problem of embedding shortest-path metrics of weighted graphs into ℓp spaces. We introduce a new embedding technique based on low-depth decompositions of a graph via shortest paths. The notion of Shortest Path Decomposition depth is inductively defined: A (weighed) path graph has shortest path decomposition (SPD) depth 1. General graph has an SPD of depth k if it contains a shortest path whose deletion leads to a graph, each of whose components has SPD depth at most k-1. In this paper we give an O(k^minfrac1p,frac12)-distortion embedding for graphs of SPD depth at most k. This result is asymptotically tight for any fixed p>1, while for p=1 it is tight up to second order terms. As a corollary of this result, we show that graphs having pathwidth k embed into ℓp with distortion O(k^minfrac1p,frac12). For p=1, this improves over the best previous bound of Lee and Sidiropoulos that was exponential in k; moreover, for other values of p it gives the first embeddings whose distortion is independent of the graph size n. Furthermore, we use the fact that planar graphs have SPD depth O(log n) to give a new proof that any planar graph embeds into ℓ1 with distortion O(√log n). Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor.