Embedding k-outerplanar graphs into l1

Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

Research output: Contribution to journalArticlepeer-review

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 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 l1 embeddings of more general metrics.

Original languageEnglish (US)
Pages (from-to)119-136
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Volume20
Issue number1
DOIs
StatePublished - Dec 1 2006
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Embedding k-outerplanar graphs into l<sub>1</sub>'. Together they form a unique fingerprint.

Cite this