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 ( n 2 ) time. We show that both problems can be solved in O ( n 2 log log n / log n ) 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 ? [ ( log n / log log n ) 2 , n 2 / 5 ] , distance queries can be answered in O ( S log S / log n ) time per query with O ( n 2 / S ) preprocessing time and space requirement. With respect to running time, this is better than previous algorithms when log S = o ( log n ) . All algorithms have linear space requirement. Our results generalize to a larger class of graphs including those with a fixed excluded minor.
wiener index shortest path distances diameter planar graph distance oracle