2008.08.26 | Else Magård

Title: Studying Road Networks Through an Algorithmic Lens

Speaker: Michael T. Goodrich, University of California, Irvine

Abstract:

This paper studies real-world road networks from an algorithmic perspective, motivated from empirical studies that yield useful properties of road networks that can be exploited in the design of fast algorithms that deal with geographic data. Unlike previous approaches, our study is not based on the assumption that road networks are planar graphs. Indeed, based on the number of experiments we have performed on the road networks of the 50 United States and District of Columbia, we provide strong empirical evidence that road networks are quite non-planar. Our approach therefore instead is directed at finding algorithmically-motivated properties of road networksas non-planar geometric graphs, focusing on alternative properties of road networks that can still lead to efficientalgorithms for such problems as shortest paths and Voronoidiagrams. Our empirical analysis uses the U.S.~TIGER/Line road network database, as provided by the Ninth DIMACS Implementation Challenge, which is comprised of over 24 million vertices and 29 million edges.

Host: Lars Arge