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

Anupam Gupta; Ilan Newman; Yuri Rabinovich; Alistair Sinclair

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

Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair

Computer Science

Research output: Contribution to journal › Conference article › peer-review

Abstract

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 l₁ 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 l₁-metrics known as 'dominating tree metrics' is shown.

Original language	English (US)
Pages (from-to)	399-408
Number of pages	10
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
State	Published - 1999
Event	Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA Duration: Oct 17 1999 → Oct 19 1999

ASJC Scopus subject areas

Hardware and Architecture

Cite this

@article{321969b3bfc0433d885c920cdfd0d11a,

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

abstract = "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.",

author = "Anupam Gupta and Ilan Newman and Yuri Rabinovich and Alistair Sinclair",

year = "1999",

language = "English (US)",

pages = "399--408",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science ; Conference date: 17-10-1999 Through 19-10-1999",

}

TY - JOUR

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

AU - Gupta, Anupam

AU - Newman, Ilan

AU - Rabinovich, Yuri

AU - Sinclair, Alistair

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0033317462&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033317462&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0033317462

SN - 0272-5428

SP - 399

EP - 408

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - Proceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science

Y2 - 17 October 1999 through 19 October 1999

ER -

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

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this