  An extremity is a vertex such that the removal of its closed neighbourhood
does not increase the number of connected components. Let $Ext_{\alpha}$ be the
class of all connected graphs whose quotient graph obtained from modular
decomposition contains no more than $\alpha$ pairwise nonadjacent extremities.
Our main contributions are as follows. First, we prove that the diameter of
every $m$-edge graph in $Ext_{\alpha}$ can be computed in deterministic ${\cal
O}(\alpha^3 m^{3/2})$ time. We then improve the runtime to linear for all
graphs with bounded clique-number. Furthermore, we can compute an additive
$+1$-approximation of all vertex eccentricities in deterministic ${\cal
O}(\alpha^2 m)$ time. This is in sharp contrast with general $m$-edge graphs
for which, under the Strong Exponential Time Hypothesis (SETH), one cannot
compute the diameter in ${\cal O}(m^{2-\epsilon})$ time for any $\epsilon > 0$.
  As important special cases of our main result, we derive an ${\cal
O}(m^{3/2})$-time algorithm for exact diameter computation within dominating
pair graphs of diameter at least six, and an ${\cal O}(k^3m^{3/2})$-time
algorithm for this problem on graphs of asteroidal number at most $k$. We end
up presenting an improved algorithm for chordal graphs of bounded asteroidal
number, and a partial extension of our results to the larger class of all
graphs with a dominating target of bounded cardinality. Our time upper bounds
in the paper are shown to be essentially optimal under plausible complexity
assumptions.
