Cuts, trees and ℓ-embeddings of graphs (preliminary version)

Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

Research output: Contribution to journalConference articlepeer-review


A systematic study is carried out focusing on the relationship between the topology of a graph and the metric distortion incurred when the graph is embedded into l1 space. Explicit constant-distortion embeddings of all series-parallel graphs, and all graphs with bounded Euler number are derived. Further, a constant-distortion embedding of outerplanar graphs into the restricted class of l1-metrics known as 'dominating tree metrics' is shown.

Original languageEnglish (US)
Pages (from-to)399-408
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 1999
EventProceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA
Duration: Oct 17 1999Oct 19 1999

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Cuts, trees and ℓ-embeddings of graphs (preliminary version)'. Together they form a unique fingerprint.

Cite this