TY - JOUR
T1 - Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time
AU - Wulff-Nilsen, Christian
N1 - EuroCG 2009
PY - 2013
Y1 - 2013
N2 - 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) time. We show that both problems can be solved in O( n2loglogn/logn) time with 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.
AB - 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) time. We show that both problems can be solved in O( n2loglogn/logn) time with 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.
U2 - 10.1016/j.comgeo.2012.01.016
DO - 10.1016/j.comgeo.2012.01.016
M3 - Journal article
SN - 0925-7721
VL - 46
SP - 831
EP - 838
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 7
ER -