Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs

Lech Duraj, Filip Konieczny, Krzysztof Potępa

We develop a framework for algorithms finding the diameter in graphs of bounded distance Vapnik-Chervonenkis dimension, in (parameterized) subquadratic time complexity. The class o…