Optimal Compression of Graph Metrics

p>Every undirected, unweighted graph G=(V,E) defines a "graph metric"
(V,d) where d is the distance function w.r.t. G. Graph spanners,
emulators, and distance oracles can all be viewed as "lossy"
compression schemes that take a (dense) undirected graph G and produce
a representation of some approximation (V,d') of the true metric
(V,d).

What does an information-theoretically optimal compression of (V,d')
look like? In particular, given a budget of n^{1+eps} bits for the
compressed representation, how much must d' diverge from d, as a
function of eps?

In this talk I will survey the history of graph compression. The talk
will cover constructions of additive spanners, sublinear additive
emulators, and a recent lower bound due to Abboud, Bodwin, and Pettie
(arXiv 2016) that mostly closes the problem.