Multivariate Analysis of Orthogonal Range Searching and Graph Distances

We show that the eccentricities, diameter, radius, and Wiener index of an undirected n -vertex graph with nonnegative edge lengths can be computed in time O(n·( [ k+⌈log n⌉; k ]) · 2^k log n) , where k is linear in the treewidth of the graph. For every ϵ >0 , this bound is n^1+ϵexp O(k) , which matches a hardness result of Abboud et al. (in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. https://doi.org/10.1137/1.9781611974331.ch28 ) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comput Geom 42:815–824, 2009. https://doi.org/10.1016/j.comgeo.2009.02.001 ) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form log ^d n to ( [ d+⌈log n⌉; d ]) , as originally observed by Monier (J Algorithms 1:60–74, 1980. https://doi.org/10.1016/0196-6774(80)90005-X ). We also investigate the parameterization by vertex cover number.