Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) VC-dimension

Overview & Synopsis

Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time (in the size n + m of the input), as shown by Roditty and Williams. Nevertheless there are several graph classes for which this can be done such as bounded-treewidth graphs, interval graphs and planar graphs, to name a few. We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many such classes-where the distance VC-dimension of a graph G is defined as the VCdimension of its ball hypergraph: whose hyperedges are the balls of all possible radii and centers in G. In particular for any fixed H, the class of H-minor free graphs has distance VC-dimension at most |V (H)| − 1.