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.