Embedding k-Outerplanar Graphs into l1

DOI10.1137/S0895480102417379zbMath1111.05022MaRDI QIDQ5470821

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

Publication date: 1 June 2006

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

metric spacesplanar graphsprobabilistic approximationmetric embeddingslow-distortion embeddings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Probabilistic metric spaces (54E70)

Related Items (14)

Coarse differentiation and multi-flows in planar graphs ⋮ Metric Embedding via Shortest Path Decompositions ⋮ Non-greedy online Steiner trees on outerplanar graphs ⋮ Stochastic approximation of lamplighter metrics ⋮ Cut-sufficient directed 2-commodity multiflow topologies ⋮ Approximating spaces of Nagata dimension zero by weighted trees ⋮ An improved algorithm for finding maximum outerplanar subgraphs ⋮ \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees ⋮ Non-greedy Online Steiner Trees on Outerplanar Graphs ⋮ Pathwidth, trees, and random embeddings ⋮ Unnamed Item ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Multicommodity flows and cuts in polymatroidal networks

This page was built for publication: Embedding k-Outerplanar Graphs into l1