Conference abstracts

Session B2 - Graph Theory and Combinatorics

July 13, 15:30 ~ 15:55 - Room B7

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

Sergio Cabello

University of Ljubljana, Slovenia   -

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.

View abstract PDF

FoCM 2017, based on a nodethirtythree design.