Let S be a set of points in the plane. In a square graph QG(S), each point is the centre of a square of bounded size. The points represent the vertices of QG(S) and two vertices share an edge, iff their squares intersect. There is a similar definition for region graphs: each point is the centre of the minimum enclosing circle of a region. Two points share an edge in the region graph RG(S), iff their respective regions intersect. We define the edge weight in both graphs to be the Euclidean distance between the endpoints of an edge.

This thesis describes routing schemes for a special case of region graphs and for the general case of square graphs that allow a packet to be routed along those graphs with a routing distance that is arbitrarily close to the optimal distance (i.e. the length of the shortest path).