Let $G$ be graph and let $d_G(u,v)$ denote the distance between vertices $u$ and $v$ of $G$.
Three key values associated to the graph are
\begin{itemize}
\item the \emph{Wiener index}, defined by $\sum_{u,v\in V(G)} d_G(u,v)$ and
closely related to the \emph{average distance} of $G$;
\item the \emph{sum of inverse geodesic lengths}, defined as $\sum_{u\neq v\in V(G)} \frac{1}{d_G(u,v)}$
and closely related to the \emph{total efficiency} of $G$;
\item the \emph{diameter}, defined by $\max\{ d_G(u,v) \mid u,v\in V(G)\}$.
\end{itemize}
All these values can be computed trivially by explicitly computing all the pairwise distances in $G$.
Can we compute these values faster, without computing all the pairwise distances?
Lower bounds assuming the Strong Exponential Time Hypothesis (SETH) were shown by Roditty and Vassilevska Williams~\cite{RVW}.
Most interestingly, if the graph has $n$ vertices and $\Theta(n)$ edges, no algorithm can compute
those values in $O(n^{1.99999})$, assuming SETH.

I will discuss how these values can be computed in subquadratic, namely $\tilde O(n^{9/5})$ time, for $n$-vertex
planar graphs and graphs on surfaces of constant genus.
The main ideas are from \cite{Cab1,Cab2}, but I will explain an alternative point of view
that represents all distances in the graph a compact way.