Networks with constant geometric dilation

Abstract

Optimization problems in network design are often modeled as graph theoretical problems, where the planar layout of the edges is neglected. A t-spanner, for instance, is a road network connecting n cities so that the shortest path between any two cities is at most t times longer than their Euclidean distance. Spanner networks are fairly well understood by now, and they can be endowed with numerous desirable properties. A good spanner, however, guarantees small detour between cities only--there may be two points in the network (halfway between cities) with arbitrary large detour. A network with constant geometric dilation connects the cities so that the detour between any two points along the network is bounded by a constant. We present an algorithm for constructing good spanner networks with constant geometric dilation for n points in the plane. We also show that some faces of such a network might have to be non-convex, and so good spanner networks typically cannot support compass routing.