Embedding k-Outerplanar Graphs into l (sub 1)

We show that the shortest-path metric of any k-outer planar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion, and hence also embedded into l1 with constant distortion. These graphs play a central role in polynomial time approximation schemes for many NP-hard optimization problems on general planar graphs, and include the family of weighted k x n planar grids. This result implies a constant upper bound on the ratio between the sparsest cut and the maximum concurrent flow in multicommodity networks for k-outer planar graphs, thus extending a classical theorem of Okamura and Seymour [OS81] for outer planar graphs, and of Gupta et al. [GNRS99] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for k-outer planar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We also conjecture that our random tree embeddings for k-outer planar graphs can serve as a building block for more powerful l1 embeddings in future.