## 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 ℓ_{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 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 ℓ_{1} embeddings in future.

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

Pages | 527-536 |

Number of pages | 10 |

State | Published - Jan 1 2003 |

Externally published | Yes |

Event | Configuralble Computing: Technology and Applications - Boston, MA, United States Duration: Nov 2 1998 → Nov 3 1998 |

### Other

Other | Configuralble Computing: Technology and Applications |
---|---|

Country/Territory | United States |

City | Boston, MA |

Period | 11/2/98 → 11/3/98 |

## ASJC Scopus subject areas

- Software
- Mathematics(all)