Embedding k-outerplanar graphs into ℓ1

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

Research output: Contribution to conferencePaperpeer-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 ℓ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 languageEnglish (US)
Pages527-536
Number of pages10
StatePublished - Jan 1 2003
Externally publishedYes
EventConfiguralble Computing: Technology and Applications - Boston, MA, United States
Duration: Nov 2 1998Nov 3 1998

Other

OtherConfiguralble Computing: Technology and Applications
Country/TerritoryUnited States
CityBoston, MA
Period11/2/9811/3/98

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

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

Cite this