Embedding k-Outerplanar Graphs into l1

DOI10.1137/S0895480102417379MaRDI QIDQ5470821zbMATH OpenFDO

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

Publication date 1 June 2006

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

Full work available at URL https://doi.org/10.1137/S0895480102417379

zbMATH Keywords

low-distortion embeddingsmetric embeddingsmetric spacesplanar graphsprobabilistic approximation

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2079381
• On embedding an outer-planar graph in a point set
• k-colored Point-set Embeddability of Outerplanar Graphs
• k-Colored Point-Set Embeddability of Outerplanar Graphs
• Bounded Embeddings of Graphs in the Plane
• scientific article; zbMATH DE number 1500196
• In-trees and plane embeddings of outerplanar graphs
• On triangulating \(k\)-outerplanar graphs
• scientific article; zbMATH DE number 3285072
• Nullspace embeddings for outerplanar graphs

Cited in

(28)

• Clin d'oeil on L₁-embeddable planar graphs
• Embedding the diamond graph in L_p and dimension reduction in L₁
• Pathwidth, trees, and random embeddings
• Non-greedy online Steiner trees on outerplanar graphs
• Non-greedy online Steiner trees on outerplanar graphs
• k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
• scientific article; zbMATH DE number 1078282 (Why is no real title available?)
• scientific article; zbMATH DE number 2079381 (Why is no real title available?)
• Nullspace embeddings for outerplanar graphs
• On triangulating \(k\)-outerplanar graphs
• Metric Embedding via Shortest Path Decompositions
• Improved guarantees for vertex sparsification in planar graphs
• A face cover perspective to ℓ₁ embeddings of planar graphs
• On the 2-sum embedding conjecture
• Improved guarantees for vertex sparsification in planar graphs
• Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
• Stochastic approximation of lamplighter metrics
• Cut-sufficient directed 2-commodity multiflow topologies
• scientific article; zbMATH DE number 7765399 (Why is no real title available?)
• 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
• An approximate generalization of the Okamura-Seymour theorem
• O(1) Steiner point removal in series-parallel graphs
• Cut-sufficient directed 2-commodity multiflow topologies
• A face cover perspective to _1 embeddings of planar graphs
• Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
• Coarse differentiation and multi-flows in planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5470821)