Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders

DOI10.1006/jctb.2000.1953zbMath1026.05032OpenAlexW1984569679MaRDI QIDQ1850474

Nathan Linial, Avner Magen

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/bf2e3cb89d732935f3f0b4fa8d559e1e7b758364

zbMATH Keywords

metric spacesEuclidean distortionoptimal embedding

Mathematics Subject Classification ID

Semidefinite programming (90C22) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (9)

Least distortion Euclidean embeddings of flat tori ⋮ Expander graphs and their applications ⋮ Speed of random walks, isoperimetry and compression of finitely generated groups ⋮ Analysis of set-up time models: a metric perspective ⋮ Optimal distortion embeddings of distance regular graphs into Euclidean spaces ⋮ L ^p -distortion and p -spectral gap of finite graphs ⋮ On the bi-Lipschitz geometry of lamplighter graphs ⋮ An average John theorem ⋮ The least Euclidean distortion constant of a distance-regular graph

Cites Work

• Unnamed Item
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On embedding expanders into \(\ell_p\) spaces
• The geometry of graphs and some of its algorithmic applications
• On embedding trees into uniformly convex Banach spaces
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• Clustering for edge-cost minimization (extended abstract)
• Geometry of cuts and metrics

This page was built for publication: Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders