Tree spanners in planar graphs
From MaRDI portal
Publication:5928870
DOI10.1016/S0166-218X(00)00226-2zbMath0969.68111MaRDI QIDQ5928870
Publication date: 4 April 2001
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (33)
On approximating tree spanners that are breadth first search trees ⋮ Tree spanners on chordal graphs: complexity and algorithms ⋮ Tree-decompositions with bags of small diameter ⋮ Well-partitioned chordal graphs ⋮ Spanners for bounded tree-length graphs ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Classes of cycle bases ⋮ Optimality computation of the minimum stretch spanning tree problem ⋮ Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms ⋮ Better hardness results for the minimum spanning tree congestion problem ⋮ Tree 3-spanners on generalized prisms of graphs ⋮ Tree spanners of bounded degree graphs ⋮ Spanners of bounded degree graphs ⋮ Three problems on well-partitioned chordal graphs ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs ⋮ Spanners in sparse graphs ⋮ Tree \(t\)-spanners in outerplanar graphs via supply demand partition ⋮ Computing a minimum-dilation spanning tree is NP-hard ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ Combinatorial network abstraction by trees and distances ⋮ The zoo of tree spanner problems ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Max-stretch reduction for tree spanners ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Spanning tree congestion of \(k\)-outerplanar graphs ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ Network flow spanners ⋮ Complexity Results for the Spanning Tree Congestion Problem ⋮ The minimum stretch spanning tree problem for typical graphs ⋮ An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs ⋮ Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction ⋮ Additive sparse spanners for graphs with bounded length of largest induced cycle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Delaunay graphs are almost as good as complete graphs
- On sparse spanners of weighted graphs
- NP-completeness of minimum spanner problems
- Design networks with bounded pairwise distance
- Graph spanners
- Planar Formulae and Their Uses
- Planar spanners and approximate shortest path queries among obstacles in the plane
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- Grid spanners
This page was built for publication: Tree spanners in planar graphs
