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

Povzetek. We show how to compute in O(n^{11/6}) expected time the diameter and the sum of the pairwise distances in a planar graph with n vertices. These are the first algorithms for this problem using time O(n^c) for some constant c<2.