Distance oracles for planar graphs

The shortest distance/path problems in planar graphs are among the most fundamental problems in graph algorithms and have numerous new applications in areas such as intelligent transportation systems which expect to get a real time answer or a distance query in large networks. A major new approach to address the new challenges is distance oracles which keep the pre-computed distance information in a data structure (called oracle) and provide an answer for a distance query with the assistance of the oracle. The preprocessing time, oracle size and query time are major criteria for evaluating two-phase algorithms. In this thesis, we first briefly review the previous work and introduce some preliminary results on exact and approximate distance oracles. Then we present our research contributions, which includes improving the preprocessing time for exact distance oracles for planar graphs with small branchwidth and providing the first constant query time (1+\epsilon)-approximate distance oracle with nearly linear size and preprocessing time for planar graphs.