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

Sergio Cabello

Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia

Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia

2017/09/26 Tue 4PM-5PM (Room

**3433**, Bldg. E6-1)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.Tags: SergioCabello