Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension

Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3

We give the first truly subquadratic time algorithm, with $O^{\ast }(n^{2-1/18})$ running time, for computing the diameter of an $n$-vertex unit-disk graph, resolving a central open prob…