Collective additive tree spanners for circle graphs and polygonal graphs

DOI10.1016/j.dam.2012.03.036zbMath1244.05216OpenAlexW2135166946MaRDI QIDQ444436

Feodor F. Dragan, Ekkehard Köhler, Yang Xiang, Derek Gordon Corneil

Publication date: 14 August 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.03.036

zbMATH Keywords

graph algorithmsbalanced separatorscircle graphscollective additive tree spannerspolygonal graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Additive tree \(O(\rho \log n)\)-spanners from tree breadth \(\rho \) ⋮ How to use spanning trees to navigate in graphs ⋮ Additive Spanners for Circle Graphs and Polygonal Graphs ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Clifford algebra and the discretizable molecular distance geometry problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• There are planar graphs almost as good as the complete graph
• Algorithmic graph theory and perfect graphs
• Additive sparse spanners for graphs with bounded length of largest induced cycle
• Graph spanners
• Recognition of Circle Graphs
• Polygon Graph Recognition
• Additive Tree Spanners
• Distributed Computing: A Locality-Sensitive Approach
• Traveling with a Pez Dispenser (or, Routing Issues in MPLS)
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Proximity-preserving labeling schemes
• Distance approximating spanning trees
• Additive graph spanners
• Collective Tree Spanners and Routing in AT-free Related Graphs
• Additive Spanners for Circle Graphs and Polygonal Graphs
• Collective tree spanners of graphs
• Graph-Theoretic Concepts in Computer Science
• Algorithms and Computation
• A tight bound on approximating arbitrary metrics by tree metrics