Constructing plane spanners of bounded degree and low weight

DOI10.1007/S00453-005-1168-8zbMATH Open1086.68136OpenAlexW2786889022MaRDI QIDQ818655FDOQ818655

Prosenjit Bose, Michiel Smid, Joachim Gudmundsson

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

Recommendations

• scientific article; zbMATH DE number 1947396
• Efficient construction of low weight bounded degree planar spanner
• Efficient construction of a bounded-degree spanner with low weight
• On bounded degree plane strong geometric spanners
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER

Mathematics Subject Classification ID

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

Cited In (30)

• Sparse hop spanners for unit disk graphs
• There are plane spanners of degree 4 and moderate stretch factor
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• On certain geometric properties of the Yao-Yao graphs
• Efficient construction of a bounded-degree spanner with low weight
• Low-light trees, and tight lower bounds for Euclidean spanners
• Minimum weight convex Steiner partitions
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• Bounded-degree plane geometric spanners in practice
• Improved spanning ratio for low degree plane spanners
• A note on optimal degree-three spanners of the square lattice
• Light orthogonal networks with constant geometric dilation
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• On the Stretch Factor of Polygonal Chains
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lattice Spanners of Low Degree
• Generating Low-Degree 2-Spanners
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• Lattice spanners of low degree
• Improved local algorithms for spanner construction
• Title not available (Why is that?)
• Vertex-colored encompassing graphs
• Lower Bounds on the Dilation of Plane Spanners
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Euclidean Steiner Spanners: Light and Sparse
• There are Plane Spanners of Maximum Degree 4
• On plane geometric spanners: a survey and open problems
• On the stretch factor of Delaunay triangulations of points in convex position
• Emanation graph: a plane geometric spanner with Steiner points

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q818655)