An efficient oracle for counting shortest paths in planar graphs

An O(\sqrt {n}) query time and O(n^{1.5}) size oracle for counting shortest paths is proposed. Given a pair of vertices u and v in a planar graph G of n vertices, the oracle answers the number of shortest paths from u to v in O(\sqrt {n}) time and whether there is a unique shortest path from u to v in O(\log n) time. Bezáková and Searns [ISAAC 2018] give an O(\sqrt {n}) query time and O(n^{1.5}) size oracle for counting shortest paths in planar graphs. Applying this oracle directly, it takes O(\sqrt {n}) time to answer whether there is a unique shortest path from u to v. A key component in our oracle is to apply Voronoi diagrams on planar graphs, which is a recent novel notion used in oracles for answering shortest distance, to speed up the query time. Computational studies show that our oracle is faster to answer queries than the oracle of Bezáková and Searns for large graphs. Our computational studies also confirm that Voronoi diagrams are efficient data structures for shortest distance oracles in practice.