Sergio Cabello, Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

We show how to compute for n-vertex planar graphs in roughly O(n^11/6) expected time the diameter and the sum of the pairwise distances. These are the first algorithms for these problems using time O(n^c) for some constant c<2, even when restricted to undirected, unweighted planar graphs.