Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension

Guillaume Ducoffe, Michel Habib, Laurent Viennot

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-…