In collaboration with

• Bar-Ilan-University and

• Tel-Aviv University.

With the proliferation of cheap mobile devices in recent years, the algorithmic study of sensor networks has received wide attention. In particular, the underlying connectivity structure poses many interesting algorithmic problems. A simple model for such a network is as follows: let S be a d-dimensional n-point set, and suppose that each site s in S has an associated radius r_s > 0. The disk transmission graph G is the directed graph with vertex set S in which there is an edge from s to t if and only if d(s, t)  <= r_s, where d(., .) is the Euclidean distance. Disk transmission graphs model the connectivity in a sensor network where each s in S corresponds to a sensor that can transmit data to all sensors within distance r_s.

We have studied the connectivity properties of disk transmission graphs from an algorithmic point of view. In particular, we were looking for reachability oracles, i.e., efficient data structures to represent and query the reachability information in such graphs. Since disk transmission graphs may be dense, it is also of interest to find sparse graphs that have the same reachability properties. In the one-dimensional case d=1, we were able to solve the problem completely. In the two-dimensional case d=2, we managed to obtain several partial results, but our investigation continues.