Bounded-degree spanners in the presence of polygonal obstacle

DOI10.1016/j.tcs.2020.12.024zbMath1477.68245OpenAlexW4206835255MaRDI QIDQ2220871

André van Renssen, Gladys Wong

Publication date: 25 January 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.12.024

zbMATH Keywords

spannerspolygonal obstaclesbounded-degree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Vertex degrees (05C07) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

Generalized sweeping line spanners ⋮ Generalized sweeping line spanners

Cites Work

• Unnamed Item
• On plane geometric spanners: a survey and open problems
• Constrained generalized Delaunay graphs are plane spanners
• On plane constrained bounded-degree spanners
• Improved spanning ratio for low degree plane spanners
• Bounded-degree spanners in the presence of polygonal obstacles
• There are plane spanners of degree 4 and moderate stretch factor
• Towards plane spanners of degree 3
• Degree four plane spanners: Simpler and better
• Geometric Spanner Networks
• Routing on the Visibility Graph
• Routing in Polygonal Domains
• Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints
• Lower Bounds on the Dilation of Plane Spanners
• Constrained routing between non-visible vertices

This page was built for publication: Bounded-degree spanners in the presence of polygonal obstacle