Friday November 3, 2006
Wean 7220, 3:30PM
L1 Embedding for Low Bandwidth Graphs
Adam Meyerson
UCLA
We introduce the first embedding of graphs of low bandwidth into L1, with distortion depending only upon the bandwidth. We extend this result to a new graph parameter called tree-bandwidth, which is very similar to (but more restrictive than) treewidth. This represents the first constant distortion embedding of a non-planar class of graphs into L1. Our results make use of a new technique that we call iterative embedding in which we define coordinates for a small number of points at a time.
Joint work with Douglas E. Carroll and Ashish Goel.
