Drawing Graphs to Speed Up Shortest-Path Computations

We consider the problem of (repeatedly) computing single- source single-target shortest paths in large, sparse graphs. Previous investigations have shown the practical usefulness of geometric speed-up techniques that guarantee the correctness of the result for shortest-path computations. However, such speed-up techniques utilize a layout of the graph which typically comes from geographic information. This paper examines the question how geometric speed-up techniques can be used in case there is no layout given. We present an extensive computational study analyzing the usefulness of methods from graph drawing as foundation for such techniques. It turns out that using appropriate layout algorithms, a significant speed-up

can be achieved. 1 Introduction Single-source single-target shortest-path computation is a fundamental algorithmic problem with manifold applications. Especially, the computation of shortest- path queries in large graphs is a common task in many application scenarios. We are particularly interested in a situation where the graph is fairly large, but sparse and an expensive preprocessing is feasible. This typically arises in routing systems where a central server operates on a static graph that is too large to admit storage of shortest paths between all pairs of vertices. Without any preprocessing, Dijkstra’s algorithm [5] is the fastest known algorithm for the general case of arbitrary non-negative edge lengths, taking O(m + nlog n) worst-case time. In [16, 24, 25, 11] however, it has been shown that a considerable speed-up for the query time can be obtained for graphs with a given layout by using the according geometric information. The aim of this paper is to examine, if these techniques can be also utilized in the absence of a given layout. Applying methods from graph drawing, layouts are ⁄This work was partially supported by the Human Potential Programme of the European Union under contract no. HPRN- CT-1999-00104 (AMORE), by the European Commission - Fet Open project COSIN - COevolution and Self-organisation In dynamical Networks - IST-2001-33555, and by the EU within the 6th Framework Programme under contract 001907 (integated project DELIS). yUniversit˜at Karlsruhe, Fakult˜at f˜ur Informatik, Institut f˜ur Logik, Komplexit˜at und Deduktionssysteme, D-76128 Karlsruhe generated and used as foundation for geometric speed- up techniques. In [4], a related question has been studied for the special case of a timetable information system. A scenario is considered where the geographic information typically contained in timetable data is incomplete. Our results are more general with respect to the graphs considered, as well as the layout algorithms explored. We experiment with real world graphs from difierent areas and with various generated graphs. In particular, in contrast to [4] no additional information is used that might support the layout algorithms (like movement of trains or coordinates of selected stations). The main contribution of this paper consists in a computational study demonstrating that artiflcially produced layouts can indeed be used as basis for geometric speed-up techniques for shortest-path computations. For several of the graphs explored, signiflcant speed-ups are achieved with appropriately generated layouts. Moreover surprisingly, for many of the tested instances where layouts based on geographic informa-...

Website: www.siam.org | Filesize: -
No of Page(s): 9
Download Drawing Graphs to Speed Up Shortest-Path Computations∗ - CiteSeer.pdf