Max Willert

Routing Schemes for Disk Graphs and Polygons

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Master of Education (M.Ed.)
Abgabedatum: 09.08.2016
Homepage des Autors:


Routing in networks is a fundamental problem that occurred in the 1980's and was well studied since then. However, there are still open problems, which have not been solved until now.

In this thesis I propose routing schemes for special graph classes. Let G=(V,E) be a weighted network or graph. For any two nodes  p, q in V, I would like to be able to route a data package from p to q. A routing scheme R assigns to each node p in V a label  l(p) from {0,1}* and a routing table rho(p) from {0,1}*. The label identifies the node in the network and the routing table is its own local read-only memory. Now the scheme works in the following way: the scheme starts with a current node p, the label of a target node and some additional information in the data package, called header. As a next step, the scheme computes a new node in the network, where the data package is forwarded to. It can use the information in the header and the local memory. The resulting sequence of nodes is the routing path. The stretch of R is the maximum ratio of the Euclidean length of the routing path and the shortest path.

Travelling in polygons is a well-known problem. The visibility graph VG(P) of a polygon P with n vertices and h holes is a graph in which two vertices in P are connected, iff they can see each other, meaning that the line segment between the two vertices is contained in P. I present the first routing scheme for polygons with holes. For any epsilon>0 the routing scheme provides the stretch 1+epsilon and uses no additional information in the header of a data package. The labels have O(log n) bits and the corresponding routing tables are of size O(epsilon^{-1} h log n). The preprocessing time is O(n^3+nh epsilon^{-1}) and can be improved for simple polygons to O(n^2+n epsilon^{-1}).