Specialeforsvar v/Jacob Secher Andersen


Distance Oracles on planar undirected graphs


An approximate distance oracle is a data structure that can query approximated distances between pairs of vertices in a graph. In this project we present an approximate distance oracle limited to undirected planar graphs. The oracle is thoroughly described, theoretically analyzed and tested in practise.

Experiments revealed that the oracle performed fairly well with returning exact distances, when run on planar graphs resembling real road maps. The oracle is not theoretically documented to efficiently query exact distances, so this was an interesting find.

An algorithm is presented for detecting non-planarities in graphs embedded in the plane. We present and experiment with modifications to the oracle to handle these non-planarities.  The modifications was shown to only perform well for graphs with limited non-planarities. Various graphs resembling real road maps fulfill these criteria.

Finally we compare the mentioned oracle with another approximate distance oracle, which can be build on non-planar graphs as well. We experimentally compare the two oracles in terms of query times, stretched distances and space usage.

Vejleder: Christian Wulff-Nilsen, associate professor, DIKU

Censor: Jesper Larsen, professor, DTU