Bandwidth and Low Dimensional Embedding

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) p, 1 ≤ p ≤ ∞. Prior to our result the only known embedding with distortion independent of n was into high dimensional `1 and had distortion exponential in k. Our low dimensional embedding is based on a general method for reducing the dimension of an `p embedding. This method requires that the embedding satisfy certain conditions, and the dimension is reduced to the intrinsic dimension of the point set, without substantially increasing the distortion. We observe that the family of graphs with bounded bandwidth are doubling, thus our main result can be viewed as a positive answer to a conjecture of Assouad [Ass83], limited to this family. We also study an extension to graphs of bounded tree-bandwidth