Title: Metric Embedding via Shortest Path Decompositions.

Author: Ittai Abraham, Arnold Filtser, Anupam Gupta and Ofer Neiman.

Abstract: We study the problem of embedding weighted graphs of pathwidth $k$
  into $\ell_p$ spaces. Our main result is an
  $O(k^{\min\{\nicefrac{1}{p},\nicefrac{1}{2}\}})$-distortion embedding.
  For $p=1$, this is a
  super-exponential improvement over the best previous bound of Lee and
  Sidiropoulos. Our distortion
  bound is asymptotically tight for any fixed $p >1$.

  Our result is obtained via a novel embedding technique that is based
  on low depth decompositions of a graph via shortest paths. The core
  new idea is that given a geodesic shortest path $P$, we can
  probabilistically embed all points into 2 dimensions with respect to $P$.
  For $p>2$ our embedding also implies improved distortion on
  bounded treewidth graphs ($O((k\log n)^{\nicefrac{1}{p}})$).
  For asymptotically large $p$, our results also implies improved distortion on graphs excluding a minor.