ROUTING. Let G be a simple, connected, undirected graph. We consider routing with preprocessing in G. In a preprocessing step, each vertex of G receives a label and a routing table. Then, we must be able to route a packet between any two vertices s and t of G, where each step may use only the label of the target node t, the routing table of the current node and the packet header. This problem has been studied extensively for general graphs, where efficient routing schemes with polylogarithmic routing tables have turned out to be impossible. Thus, special graph classes are of interest.

Let P be an x-monotone orthogonal polygon with n vertices. We call P a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizontal chord from the left boundary to the right boundary. Two points p and q in P are co-visible if and only if the (axis-parallel) rectangle spanned by p and q completely lies in P. In the r-visibility graph Vis(P) of P, we connect two vertices of P with a unit weighted edge if and only if they are co-visible. We present a routing scheme for visibility graphs of simple and of double histograms that have label size log n and table size O(log n deg(v)) for each vertex v of P, where deg(v) is the degree of v in Vis(P). In simple histograms we can route along a shortest path and need no additional header, whereas in double histograms we need headers of size log n and we can route on a path that has twice the length of an optimal path. The preprocessing time is in both cases O(m), where m is the number of edges in Vis(P).

Let V be a set of n sites in the plane. The unit disk graph DG(V) of V is the graph with vertex set V where two sites v and w are adjacent if and only if their Euclidean distance is at most 1. The edge weights correspond to the Euclidean distance of its endpoints. Moreover, we use D to denote the diameter of DG(V). We show that for any given eps>0, we can construct a routing scheme for DG(V) that achieves stretch 1+eps, has label size O(eps^(-1)log D log^3n/loglog n), table size eps^(-O(eps^(-2)))log^3n(1+log D/loglog n) and the header needs at most O(log^2n/loglog n) bits. The preprocessing time is O(eps^(-1)n^2 log^2 n).

STABBING. Suppose we are given a set D of n pairwise intersecting disks in the plane. A planar point set P stabs D if and only if each disk in D contains at least one point from P. We present a deterministic algorithm that takes O(n) time to find five points that stab D. This provides a simple---albeit slightly weaker---algorithmic version of a classical result by Danzer that such a set D can always be stabbed by four points. Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points.