## Abstract

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 l_{1} 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 theorem of Okamura and Seymour [J. Combin. Theory Ser. B, 31 (1981), pp. 75-81] for outerplanar graphs, and a result of Gupta et al. [Combinatorica, 24 (2004), pp. 233-269] 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 conjecture that these embeddings for k-outerplanar graphs may serve as building blocks for l_{1} embeddings of more general metrics.

Original language | English (US) |
---|---|

Pages (from-to) | 119-136 |

Number of pages | 18 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 20 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1 2006 |

Externally published | Yes |

## Keywords

- Low-distortion embeddings
- Metric embeddings
- Metric spaces
- Planar graphs
- Probabilistic approximation
- k-outerplanar graphs

## ASJC Scopus subject areas

- Mathematics(all)