# Sparse Hop Spanners for Unit Disk Graphs

@article{Dumitrescu2020SparseHS, title={Sparse Hop Spanners for Unit Disk Graphs}, author={Adrian Dumitrescu and Anirban Ghosh and Csaba D. T'oth}, journal={ArXiv}, year={2020}, volume={abs/2002.07840} }

A unit disk graph $G$ on a given set of points $P$ in the plane is a geometric graph where an edge exists between two points $p,q \in P$ if and only if $|pq| \leq 1$. A subgraph $G'$ of $G$ is a $k$-hop spanner if and only if for every edge $pq\in G$, the topological shortest path between $p,q$ in $G'$ has at most $k$ edges. We obtain the following results for unit disk graphs.
(i) Every $n$-vertex unit disk graph has a $5$-hop spanner with at most $5.5n$ edges. We analyze the family of… Expand

#### 2 Citations

Efficient Communication in Large Multi-robot Networks

- Computer Science
- 2020 IEEE International Conference on Robotics and Automation (ICRA)
- 2020

The proposed communication model is generic to any type of message and guarantees a low hop routing between any pair of robots in this network and easily scales up to 1000 robots while drastically reducing the space complexity for maintaining the network information. Expand

An Interactive Tool for Experimenting with Bounded-Degree Plane Geometric Spanners (Media Exposition)

- Computer Science
- SoCG
- 2021

This work has implemented seven sophisticated algorithms for bounded-degree plane geometric spanners using JSXGraph, a state-of-the-art JavaScript library for geometry, so that they can be used for further research and teaching computational geometry. Expand

#### References

SHOWING 1-10 OF 52 REFERENCES

Plane Hop Spanners for Unit Disk Graphs: Simpler and Better

- Mathematics, Computer Science
- Comput. Geom.
- 2020

This paper presents a simple algorithm that constructs a plane hop spanner for the unit disk graph, a widely employed model for the study of wireless networks, and establishes several results on the plane geometry. Expand

On Geometric Spanners of Euclidean and Unit Disk Graphs

- Mathematics, Computer Science
- STACS
- 2008

A very simple linear time algorithm is obtained that, given a unit disk graph embedded in the plane, constructs a geometric spanner with the above stretch factor and degree bound, and also containing an EMST as a subgraph. Expand

Lower Bounds on the Dilation of Plane Spanners

- Computer Science, Mathematics
- Int. J. Comput. Geom. Appl.
- 2016

(I) We exhibit a set of 23 points in the plane that has dilation at least $1.4308$, improving the previously best lower bound of $1.4161$ for the worst-case dilation of plane spanners.
(II) For… Expand

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

- Mathematics
- 2007

Let G = (V,E) be an undirected weighted graph on |V | = n vertices and |E| = m edges. A t-spanner of the graph G, for any t ≥ 1, is a subgraph (V,ES), ES ⊆ E, such that the distance between any pair… Expand

Simple Algorithms for Spanners in Weighted Graphs

- Mathematics, Computer Science
- Encyclopedia of Algorithms
- 2016

The objective is to design an algorithm that, for any weighted graph on n vertices, computes a .2k 1/-spanner of O.n1C1=k/ size, and the most ambitious aim would be to achieve the linear time complexity. Expand

Generating low-degree 2-spanners

- Mathematics, Computer Science
- SODA '94
- 1994

It is shown that the problem of finding a 2-spanner in a given graph is at least as hard to approximate as set cover, and a randomized approximation algorithm is provided with approximation ratio of $\tilde O(\Delta^{1/4})$. Expand

Planar Hop Spanners for Unit Disk Graphs

- Computer Science
- ALGOSENSORS
- 2010

This paper presents an algorithm that, given a set X of terminals in the plane, constructs a planar hop spanner with constant stretch factor for the Unit Disk Graph defined by X, and improves on previous constructions in the sense that it ensures the planarity of the whole spanner. Expand

Plane Hop Spanners for Unit Disk Graphs

- Mathematics, Computer Science
- WADS
- 2019

The unit disk graph (UDG) is a widely employed model for the study of wireless networks and a hop spanner is a spanning subgraph H such that for every edge in the UDG the topological shortest path between p and q in H has a constant number of edges. Expand

Efficient construction of low weighted bounded degree planar spanner

- Mathematics, Computer Science
- Int. J. Comput. Geom. Appl.
- 2004

This work gives an O(nlogn)-time centralized algorithm that constructs a planar t-spanner for V, for such that the degree of each node is bounded from above by , where 0<α<π/2 is an adjustable parameter. Expand

Efficient Construction of Low Weight Bounded Degree Planar Spanner

- Mathematics, Computer Science
- COCOON
- 2003

This method can be converted to a localized algorithm where the total number of messages sent by all nodes is at most O(n) (under broadcasting communication model) and the constants are all worst case constants due to the proofs. Expand