We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in \tilde O(nb^2) time \tilde  so that one can compute any additively weighted Voronoi diagram for these sites in \tilde O(b) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in O(n^{5/3}) time. This improves the recent breakthrough result of Cabello (SODA'17), both by improving the running time (from O(n^{11/6})), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic {\em  algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can also computethe Wiener index of a planar graph (i.e., the sum of all pairwise distances)  within the same bound . Our construction of Voronoi diagrams for planar graphs is of independent interest . It has already been used to obtain fast exact distance oracles for planar graphs Cohen-Addad et al., FOCS'17 .
We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in \tilde O(nb^2) time (footnote: The\tilde O notation hides polylogarithmic factors.) so that one can compute any additively weighted Voronoi diagram for these sites in \tilde O(b) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in O(n^{5/3}) time. This improves the recent breakthrough result of Cabello (SODA'17), both by improving the running time (from O(n^{11/6})), and by providing a deterministic algorithm. It is in fact the first truly subquadratic {\em deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can compute, for every vertex v, both the farthest vertex from v (i.e., the eccentricity of v), and the sum of distances from v to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all pairwise distances) of a planar graph within the same time bounds . Our construction of Voronoi diagrams for planar graphs is of independent interest .
A
(footnote: The
A
O notation hides polylogarithmic factors.)
D
deterministic
A
deterministic
R
also computethe Wiener index of a planar graph
compute, for every vertex v, both the farthest vertex from v
R
sum of all
eccentricity of v), and the sum of distances from v to all other vertices. Hence, our algorithm can also compute the radius, median, and Wiener index (sum of all
A
of a planar graph
R
bound
time bounds
D
. It has already been used to obtain fast exact distance oracles for planar graphs
D
Cohen-Addad et al., FOCS'17