Routing in Unit Disk Graphs
Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico, 2016
Let S be a set of n sites in the plane. The unit disk graph UD(S) on S has vertex set S and an edge between two distinct sites s,t in S if and only if s and t have Euclidean distance |st| <= 1. A routing scheme R for UD(S) assigns to each site s in S a label l(s) and a routing table rho(s). For any two sites s,t in S, the scheme R must be able to route a packet from s to t in the following way: given a current site r (initially, r=s), a header h (initially empty), and the target label l(t), the scheme R may consult the current routing table rho(r) to compute a new site r′ and a new header h′, where r′ is a neighbor of r. The packet is then routed to r′, and the process is repeated until the packet reaches t. The resulting sequence of sites is called the routing path. The stretch of R is the maximum ratio of the (Euclidean) length of the routing path produced by R and the shortest path in UD(S), over all pairs of distinct sites in S.
For any given eps>0, we show how to construct a routing scheme for UD(S) with stretch 1+eps using labels of O(logn) bits and routing tables of O(eps^-5 log^2(n) log^2(D)) bits, where D is the (Euclidean) diameter of UD(S). The header size is O(log(n)log(D)) bits.