Embedding k-outerplanar graphs into e1
Lists
Only you see this
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 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 × 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 l1 embeddings in future.
BibTeX
@inproceedings{chekuri2003embedding,
author = {Chandra Chekuri and Anupam Gupta and Ilan Newman and Yuri Rabinovich and Alistair Sinclair},
title = {{Embedding k-outerplanar graphs into e1}},
booktitle = {SODA},
year = {2003},
url = {https://openreview.net/forum?id=qKKl3OODMT},
}Loading related content...