עופר נימן

We study the problem of embedding weighted graphs of pathwidth k into ℓ_p spaces. Our main result is an O(k^min {1/p^{, 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)¹/^p)). For asymptotically large p, our results also implies improved distortion on graphs excluding a minor.