Paper Info

Title | ||
---|---|---|

Embedding k-Outerplanar Graphs into l1 |

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 $\ell_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\times 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 $\ell_1$ embeddings of more general metrics. |

Year | DOI | Venue |
---|---|---|

2003 | 10.1137/S0895480102417379 | SODA |

Keywords | DocType | Volume |

constant distortion,polynomial time approximation scheme,outerplanar graph,approximation ratio,tree metrics,k-Outerplanar Graphs,general metrics,planar grid,approximation algorithm,general planar graph,probabilistic tree embeddings | Conference | 20 |

Issue | ISSN | Citations |

1 | 0895-4801 | 18 |

PageRank | References | Authors |

1.16 | 14 | 5 |

Authors (5 rows)

Cited by (18 rows)

References (14 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Chandra Chekuri | 1 | 3493 | 293.51 |

Anupam Gupta | 2 | 2989 | 210.44 |

Ilan Newman | 3 | 1149 | 82.18 |

Yuri Rabinovich | 4 | 18 | 1.16 |

Alistair Sinclair | 5 | 1506 | 308.40 |