Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time

Let G be an n-vertex planar, undirected, and unweighted graph. It was stated as open problems whether the Wiener index, defined as the sum of all-pairs shortest path distances, and the diameter of G   can be computed in o(n2)o(n2) time. We show that both problems can be solved in O(n2loglogn/logn) time with O(n)O(n) space. The techniques that we apply allow us to build, within the same time bound, an oracle for exact distance queries in G  . More generally, for any parameter S∈[(logn/loglogn)2,n2/5], distance queries can be answered in O(SlogS/logn) time per query with O(n2/S) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when logS=o(logn). All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.