  We study the problem of embedding shortest-path metrics of weighted graphs
into $\ell_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^{\min\{\frac{1}{p},\frac{1}{2}\}})$-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 $\ell_p$ with distortion $O(k^{\min\{\frac{1}{p},\frac{1}{2}\}})$. 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 $\ell_1$ with distortion $O(\sqrt{\log
n})$. Our approach also gives new results for graphs with bounded treewidth,
and for graphs excluding a fixed minor.
