We present a deterministic algorithm that computes\tilde \tilde  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 using a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our algorithm follows the general high-level approach of Cabello, but differs in the way it is implemented. Our main technical contribution is an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs (under the assumption that all Voronoi sites lie on a constant number of faces). The idea of using Voronoi diagrams is also borrowed from Cabello, except that he uses abstract Voronoi diagrams (as a black box) , which makes the implementation more involved, more expensive, and randomized. Our explicit construction avoids these issues, and leads to the improved (and deterministic) running time. As in Cabello's work, our algorithm can also compute the Wiener index of ( sum of all pairwise distances in) a planar graph, within the same bounds  .
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 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 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 compute the 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 .
R
a deterministic algorithm that computes
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
A
O(nb^2) time so that one can compute any additively weighted Voronoi diagram for these sites in
A
O(b) time. We use this construction to compute
R
using
providing
R
algorithm follows the general high-level approach of Cabello, but differs in the way it is implemented. Our main technical contribution is an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs (under the assumption that all Voronoi sites lie on a constant number of faces). The idea of using Voronoi diagrams is also borrowed from Cabello, except that he uses
use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used
D
(as a black box)
R
the implementation
his diameter algorithm
D
Our explicit construction avoids these issues, and leads to the improved (and deterministic) running time.
R
(
a planar graph (i.e., the
R
in) a planar graph,
)
R
bounds
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
A
Cohen-Addad et al., FOCS'17