Cuts, trees and `1-embeddings of graphs

Motivated by many recent algorithmic applications, this paper aims to promote a systematic study of the relationship between the topology of a graph and the metric distortion incurred when the graph is embedded into ` 1 space. The main results are: 1. Explicit constant-distortion embeddings of all series-parallel graphs, and all graphs with bounded Euler number. These are the rst natural families known to have constant dis-tortion (strictly greater than 1). Using the above embeddings, algorithms are obtained which approximate the sparsest cut in such graphs to within a constant factor. 2. A constant-distortion embedding of outerplanar graphs into the restricted class of ` 1 metrics known as \dominating tree metrics". A lower bound of (logn) on the distortion for embeddings of series-parallel graphs into (distributions over) dominating tree metric