Title: Bandwidth and Low Dimensional Embedding

Authors: Yair Bartal, Douglas E. Carroll, Adam Meyerson and Ofer Neiman

Abstract: 

We design an algorithm to embed graph metrics into L_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 L_p, 1 \le p \le \infty. Prior
to our result the only known embedding with distortion independent
of n was into high dimensional L_1 and had distortion exponential in
k. Our low dimensional embedding is based on a general method for
reducing dimension in an L_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, limited to this family. We also study an
extension to graphs of bounded tree-bandwidth.