On plane constrained bounded-degree spanners

DOI10.1007/s00453-018-0476-8zbMath1422.68242arXiv1704.03596OpenAlexW2881370671WikidataQ129643239 ScholiaQ129643239MaRDI QIDQ1739100

Rolf Fagerberg, Sander Verdonschot, André van Renssen, Prosenjit Bose

Publication date: 25 April 2019

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

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

zbMATH Keywords

constraintsvisibility graphbounded-degreeplane spanners

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (15)

Constrained generalized Delaunay graphs are plane spanners ⋮ Upper and Lower Bounds for Online Routing on Delaunay Triangulations ⋮ On plane geometric spanners: a survey and open problems ⋮ Generalized sweeping line spanners ⋮ Generalized sweeping line spanners ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Plane hop spanners for unit disk graphs: simpler and better ⋮ Bounded-degree spanners in the presence of polygonal obstacle ⋮ On plane constrained bounded-degree spanners ⋮ Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ Constrained routing between non-visible vertices ⋮ Drawing graphs as spanners ⋮ There are plane spanners of degree 4 and moderate stretch factor ⋮ Routing on the visibility graph

Cites Work

• On plane geometric spanners: a survey and open problems
• Constrained generalized Delaunay graphs are plane spanners
• On plane constrained bounded-degree spanners
• There are plane spanners of degree 4 and moderate stretch factor
• Degree four plane spanners: Simpler and better
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• Geometric Spanner Networks
• Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles
• Plane Spanners of Maximum Degree Six
• Upper Bounds on the Spanning Ratio of Constrained Theta-Graphs

This page was built for publication: On plane constrained bounded-degree spanners