עופר נימן

We design an algorithm to embed graph metrics into ℓ_p with dimension and distortion both dependent only upon the bandwidth of the graph. In particular we show that any graph of bandwidth k embeds with distortion polynomial in k into O(log k) dimensional ℓ_p, 1 ≤ p ≤ ∞. Prior to our result the only known embedding with distortion independent of n was into high dimensional ℓ₁ and had distortion exponential in k. Our low dimensional embedding is based on a general method for reducing dimension in an ℓ_p embedding, satisfying certain conditions, to the intrinsic dimension of the point set, without substantially increasing the distortion. As we observe that the family of graphs with bounded bandwidth are doubling, our result can be viewed as a positive answer to a conjecture of Assouad [2], limited to this family. We also study an extension to graphs of bounded tree-bandwidth.