We study the problem of computing the diameter and the mean distance of a continuous graph, i. e. , a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with m edges these values can be computed in roughly O (m²) time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most k can be computed in O (n^O (k) n) time, where n is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with n vertices and F faces takes O (n F n) time.
Cabello et al. (Mon,) studied this question.