Embedding k-outerplanar graphs into ℓ₁

We show that the shortest-path metric of any k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion, and hence also embedded into ℓ₁ 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 × 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-outerplanar graphs, thus extending a classical theorem of Okamura and Seymour [26] for outerplanar graphs, and of Gupta et al. [17] for treewidth-2 graphs. In addition, we obtain improved approximation ratios for k-outerplanar graphs on various problems for which approximation algorithms are based on probabilistic tree embeddings. We also conjecture that our random tree embeddings for k-outerplanar graphs can serve as a building block for more powerful ℓ₁ embeddings in future.