k-outerplanar graphs, planar duality, and low stretch spanning trees
DOI10.1007/S00453-010-9423-ZzbMATH Open1223.05040OpenAlexW2163098772MaRDI QIDQ634672FDOQ634672
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
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
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- A tight bound on approximating arbitrary metrics by tree metrics
- Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen
- Optimum Communication Spanning Trees
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Excluded minors, network decomposition, and multicommodity flow
- Cuts, trees and \(\ell_1\)-embeddings of graphs
- Lower-Stretch Spanning Trees
- Embedding k-Outerplanar Graphs into l1
- Probabilistic embeddings of bounded genus graphs into planar graphs
- On approximating planar metrics by tree metrics.
- A tight upper bound on the probabilistic embedding of series-parallel graphs
Cited In (5)
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)
