  We propose to study unweighted graphs of constant distance VC-dimension as a
broad generalization of many graph classes for which we can compute the
diameter in truly subquadratic-time. In particular for any fixed $H$, the class
of $H$-minor free graphs has distance VC-dimension at most $|V(H)|-1$. Our
first main result is that on graphs of distance VC-dimension at most $d$, for
any fixed $k$ we can either compute the diameter or conclude that it is larger
than $k$ in time $\tilde{\cal O}(k\cdot mn^{1-\varepsilon_d})$, where
$\varepsilon_d \in (0;1)$ only depends on $d$. Then as a byproduct of our
approach, we get the first truly subquadratic-time algorithm for constant
diameter computation on all the nowhere dense graph classes. Finally, we show
how to remove the dependency on $k$ for any graph class that excludes a fixed
graph $H$ as a minor. More generally, our techniques apply to any graph with
constant distance VC-dimension and polynomial expansion. As a result for all
such graphs one obtains a truly subquadratic-time algorithm for computing their
diameter. Our approach is based on the work of Chazelle and Welzl who proved
the existence of spanning paths with strongly sublinear stabbing number for
every hypergraph of constant VC-dimension. We show how to compute such paths
efficiently by combining the best known approximation algorithms for the
stabbing number problem with a clever use of $\varepsilon$-nets, region
decomposition and other partition techniques.
