# Routing in Unit Disk Graphs

### Wednesday, November 2nd, 2016, 16:10

### Schreiber 309

### Routing in Unit Disk Graphs

### Paul Seiferth, FU Berlin

### Abstract:

Let S be a set of n point-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 of 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 of 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 procedure 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(log(n)) 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.

The unit disk graph UD(S) on S has vertex set S and an edge

between two distinct sites s,t of 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 of 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 procedure 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(log(n)) 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.