Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia

**3433**, Bldg. E6-1)

^{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.