Bounded-degree spanners in the presence of polygonal obstacle

DOI10.1016/J.TCS.2020.12.024MaRDI QIDQ2220871zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Spanners for geodesic graphs and visibility graphs
• Geometric Spanners for Points Inside a Polygonal Domain
• Constructing plane spanners of bounded degree and low weight

Cites work

• Bounded-degree spanners in the presence of polygonal obstacles
• Competitive local routing with constraints
• Constrained generalized Delaunay graphs are plane spanners
• Degree four plane spanners: simpler and better
• Geometric Spanner Networks
• Lower bounds on the dilation of plane spanners
• On plane geometric spanners: a survey and open problems
• Routing in polygonal domains
• Routing on the Visibility Graph
• Spanning properties of Yao and \(\theta\)-graphs in the presence of constraints
• There are plane spanners of degree 4 and moderate stretch factor
• Towards plane spanners of degree 3

Cited in

(6)

• Efficient construction of a bounded-degree spanner with low weight
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• Generalized sweeping line spanners
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Generalized sweeping line spanners
• Spanners for geodesic graphs and visibility graphs

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

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