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

DOI10.1007/s00453-010-9423-zzbMath1223.05040OpenAlexW2163098772MaRDI QIDQ634672

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

planar graphsouterplanarityaverage stretchplanar dual

Mathematics Subject Classification ID

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

Related Items (1)

On minimum average stretch spanning trees in polygonal 2-trees

Cites Work

• Cuts, trees and \(\ell_1\)-embeddings of graphs
• On approximating planar metrics by tree metrics.
• Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen
• Optimum Communication Spanning Trees
• A tight upper bound on the probabilistic embedding of series-parallel graphs
• Lower-Stretch Spanning Trees
• Approximation algorithms for NP-complete problems on planar graphs
• A Graph-Theoretic Game and Its Application to the k-Server Problem
• Excluded minors, network decomposition, and multicommodity flow
• Embedding k-Outerplanar Graphs into l1
• A tight bound on approximating arbitrary metrics by tree metrics
• Unnamed Item
• Unnamed Item
• Unnamed Item

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