- Series
- Graph Theory Seminar
- Time
- Tuesday, February 24, 2026 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Da Zheng – IST Austria – https://zhengdw.github.io/
- Organizer
- Xiying Du and Rose McCarty
A simple algorithm for computing the diameter of an unweighted $n$-vertex graph is to run a BFS from every vertex of the graph. This leads to quadratic time algorithms for computing diameter in sparse graphs and geometric intersection graphs. There are matching fine-grained lower bounds which show that in many cases, it is not possible to get a truly subquadratic time algorithm for diameter computation.
To contrast, we give the first truly subquadratic time algorithm for computing the diameter of an $n$-vertex unit-disk graph. The algorithm runs in with $O^*(n^{2-1/18})$ time. The result is obtained as an instance of a general framework, applicable for distance problems in any graph with bounded distance VC-dimension. To obtain these results, we exploit bounded VC-dimension of neighborhood balls, low-diameter decompositions, and geometric data structures.
Based on paper in FOCS 2025, joint work with Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, and Hung Le. Arxiv: https://arxiv.org/abs/2510.16346