Improved spanning ratio for low degree plane spanners

DOI10.1007/s00453-017-0305-5zbMath1390.68711arXiv1506.09061OpenAlexW2951836815MaRDI QIDQ1742372

Prosenjit Bose, Darryl Hill, Michiel H. M. Smid

Publication date: 11 April 2018

Published in: Algorithmica, LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.09061

zbMATH Keywords

graph theorydegreegraphscomputational geometryspannersplanebounded degreespanning ratiospanning graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (4)

Geometric spanning trees minimizing the Wiener index ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ Unnamed Item ⋮ Bounded-degree spanners in the presence of polygonal obstacle

Cites Work

• Unnamed Item
• On bounded degree plane strong geometric spanners
• Delaunay graphs are almost as good as complete graphs
• Constructing plane spanners of bounded degree and low weight
• Classes of graphs which approximate the complete Euclidean graph
• There are plane spanners of degree 4 and moderate stretch factor
• The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
• On Spanners and Lightweight Spanners of Geometric Graphs
• Efficient Construction of Low Weight Bounded Degree Planar Spanner
• Degree Four Plane Spanners: Simpler and Better
• Plane Spanners of Maximum Degree Six
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE

This page was built for publication: Improved spanning ratio for low degree plane spanners