text: 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 @math , the class of @math -minor free graphs has distance VC-dimension at most @math . Our first main result is that on graphs of distance VC-dimension at most @math , for any fixed @math we can either compute the diameter or conclude that it is larger than @math in time @math , where @math only depends on @math . 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 @math for any graph class that excludes a fixed graph @math 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 @math -nets, region decomposition and other partition techniques.
  @cite_0: The computational problem of finding the center of a graph is motivated by a number of facility-location problems. We exploit a new characterization of interval graphs for the purpose of obtaining a linear-time algorithm for computing both the center and the diameter of an interval graph.
  @cite_31: 
  @cite_23: Determining the diameter of a graph is a fundamental graph operation, yet no efficient (i.e. linear or quadratic time) algorithm is known. In this paper, we examine the diameter problem on chordal graphs and AT-free graphs and show that a very simple (linear time) 2-sweep LexBFS algorithm identifies a vertex of maximum eccentricity unless the given graph has a specified induced subgraph (it was previously known that a single LexBFS algorithm is guaranteed to end at a vertex that is within 1 of the diameter for chordal graphs and AT-free graphs). As a consequence of the forbidden induced subgraph result on chordal graphs, our algorithm is guaranteed to work optimally for directed path graphs (it was previously known that a single LexBFS algorithm is guaranteed to work optimally for interval graphs).
summary: An early example of linear-time solvable special case for diameter computation is the class of interval graphs @cite_0 . For every interval graph @math and for any integer @math , if we first compute an interval representation for @math in linear-time @cite_31 then we can compute by dynamic programming, for every vertex @math , the contiguous segment of all the vertices at a distance @math from @math in @math . It takes almost linear-time and it implies a straightforward quasi linear-time algorithm for diameter computation. More efficient algorithms for diameter computation on interval graphs and related graph classes were proposed in @cite_23 . Nevertheless we will show in what follows that interval orderings are a powerful tool for diameter computation on more general geometric graph classes.