k-outerplanar graphs, planar duality, and low stretch spanning trees

DOI10.1007/S00453-010-9423-ZMaRDI QIDQ634672zbMATH OpenOpenAlexFDO

Authors Yuval Emek

Publication date 16 August 2011

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-010-9423-z

zbMATH Keywords

average stretchouterplanarityplanar dualplanar graphs

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
• scientific article; zbMATH DE number 2079381
• Embedding k-Outerplanar Graphs into l1
• Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
• Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs

Cites work

• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A tight bound on approximating arbitrary metrics by tree metrics
• A tight upper bound on the probabilistic embedding of series-parallel graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Embedding k-Outerplanar Graphs into l1
• Excluded minors, network decomposition, and multicommodity flow
• scientific article; zbMATH DE number 1775400 (Why is no real title available?)
• scientific article; zbMATH DE number 830463 (Why is no real title available?)
• Lower-Stretch Spanning Trees
• On approximating planar metrics by tree metrics.
• Optimum Communication Spanning Trees
• Probabilistic embeddings of bounded genus graphs into planar graphs
• Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen

Cited in

(6)

• On minimum average stretch spanning trees in polygonal 2-trees
• A tight upper bound on the probabilistic embedding of series-parallel graphs
• k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
• scientific article; zbMATH DE number 2079381 (Why is no real title available?)
• On triangulating \(k\)-outerplanar graphs
• Survivable network design with group-to-group requirement

This page was built for publication: \(k\)-outerplanar graphs, planar duality, and low stretch spanning trees

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