Constructing plane spanners of bounded degree and low weight

DOI10.1007/s00453-005-1168-8zbMath1086.68136OpenAlexW2786889022MaRDI QIDQ818655

Prosenjit Bose, Joachim Gudmundsson, Michiel H. M. Smid

Publication date: 21 March 2006

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-005-1168-8

Mathematics Subject Classification ID

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

Related Items (23)

Sparse hop spanners for unit disk graphs ⋮ Euclidean Steiner Spanners: Light and Sparse ⋮ On plane geometric spanners: a survey and open problems ⋮ On the stretch factor of Delaunay triangulations of points in convex position ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ On certain geometric properties of the Yao-Yao graphs ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ Unnamed Item ⋮ Improved spanning ratio for low degree plane spanners ⋮ Minimum weight convex Steiner partitions ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ Improved local algorithms for spanner construction ⋮ Unnamed Item ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ Vertex-colored encompassing graphs ⋮ Light orthogonal networks with constant geometric dilation ⋮ DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE ⋮ Lattice spanners of low degree ⋮ On the Stretch Factor of Polygonal Chains ⋮ A note on optimal degree-three spanners of the square lattice ⋮ There are plane spanners of degree 4 and moderate stretch factor

This page was built for publication: Constructing plane spanners of bounded degree and low weight