Wiener Index, Diameter, and Stretch Factor of a Planar Graph in Subquadratic Time

Christian Wulff-Nilsen, Department of Computer Science, University of Copenhagen

We consider the following three open problems: can the Wiener index and diameter of a planar digraph with real edge weights and with no negative weight cycles, and the stretch factor of a plane geometric graph be computed in subquadratic time? We solve all three problems by giving algorithms with O(n2(loglog n)4/log n) running time, where n is the size of the graph. All results are obtained from the same generic algorithm. Another corollary is that we can answer exact distance queries in constant time with subquadratic preprocessing time.