Collective additive tree spanners for circle graphs and polygonal graphs

DOI10.1016/j.dam.2012.03.036zbMath1244.05216MaRDI 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 algorithms; balanced separators; circle graphs; collective additive tree spanners; polygonal graphs

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Additive Spanners for Circle Graphs and Polygonal Graphs, Clifford algebra and the discretizable molecular distance geometry problem, How to use spanning trees to navigate in graphs, On polygon numbers of circle graphs and distance hereditary graphs

Cites Work

• Unnamed Item
• 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
• 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