Sparse hop spanners for unit disk graphs

DOI10.1016/j.comgeo.2021.101808zbMath1479.05080arXiv2002.07840OpenAlexW3116535447MaRDI QIDQ824328

Adrian Dumitrescu, Anirban Ghosh, Csaba D. Tóth

Publication date: 15 December 2021

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

lower boundunit disk graph\( \epsilon \)-netgraph approximationhop-spanner

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph theory (05C99) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unsplittable coverings in the plane
• On plane geometric spanners: a survey and open problems
• Delaunay graphs are almost as good as complete graphs
• Constructing plane spanners of bounded degree and low weight
• Sparse geometric graphs with small dilation
• Steiner minimal trees for regular polygons
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• On sparse spanners of weighted graphs
• Unit disk graph recognition is NP-hard
• Plane hop spanners for unit disk graphs: simpler and better
• An improved upper bound on dilation of regular polygons
• Bounded-hops power assignment in ad hoc wireless networks
• The number of disk graphs
• Lattice spanners of low degree
• Graph Theory
• Geometric Spanner Networks
• On the shape of a set of points in the plane
• Steiner Minimal Tree for Points on a Circle
• Graph spanners
• Generating Low-Degree 2-Spanners
• Generating Sparse 2-Spanners
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Tight lower bounds for the size of epsilon-nets
• Approximation schemes for wireless networks
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Lower Bounds on the Dilation of Plane Spanners