Many distances in planar graphs
Sergio Cabello · University of Maribor digital library (University of Maribor) · 2006
We show how to compute in O(n 4/3 log 1/3 n + n 2/3 k 2/3 log n) time the distance between k given pairs of vertices of a planar graph G with n vertices. This improves previous results whenever (n / log n) 5/6 ≤ k ≤ n 2 / log 6 n. As an application, we speed up previous algorithms for computing the dilation of geometric planar graphs.