Online routing in geometric graphs

Abstract

This thesis considers the problem of finding a path from a source to a destination in a graph in which only local information is available. This type of routing problem occurs regularly in robotics, parallel and distributed computing, mobile networks, and everyday life. In particular, the research focuses on the case where the graph is geometric (nodes of the graph have locations in space) and planar (edges of the graph do not cross). The results in this thesis fall into four categories: (1) natural and intuitive algorithms that work on some well known and structured geometric graphs, (2) algorithms for special classes of graphs that find paths approximating shortest paths, (3) algorithms for arbitrary planar graphs, (4) algorithms for embedding graphs nicely so that simple algorithms can be used to find paths between vertices, and (5) simulation results that help to determine which routing algorithms work best in different settings. In studying these problems we draw on a wide range of techniques from computer science and mathematics, improve some previous results, and report a number of open problems and directions for continuing research.