Space-approximation Trade-off In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(2k-1)$-approximate distance between any pair of  vertices in the graph.

At a fundamental level, this construction achieves a space-approximation trade-off --- one can reduce the space requirements at the cost of a lower "quality" of the solution.


  What other graph problems exhibit such a trade-off between space and approximation?


I am interested in the case of both static and dynamic, weighted and unweighted, undirected and directed graphs.

Thanks.
this research appears to be active in a more applied sense than the theoretical one you mention (ie oracles etc) with "data streaming" algorithms which attempt to work with very large data through "sliding windows", with many graph algorithms considered, but it is indeed relatively new/recent, fitting in with "big data" research directions.


Tradeoff Algorithms in Streaming Models, Andrea Ribichini, p7:



  We have devised several algorithms for fundamental graph problems in the
  W-Stream model, including connected components, minimum spanning tree,
  biconnected components and single-source shortest paths. To the best of
  our knowledge, our algorithms are the first to allow effective space/passes
  tradeoffs for such problems in a data streaming setting.


this ref includes other refs/surveys which might be helpful.


  Despite the heavy restrictions imposed by the [classical streaming] model, major success has
  been achieved for several data sketching and statistics problems, for which
  a constant number of passes and polylogarithmic working memory have
  been proven enough to find approximate solutions (see [4, 16, 17] and the
  extensive bibliographies in [7, 29]).


also: 


Trading off space for passes in graph streaming problems
Camil Demetrescu,
Irene Finocchi,
Andrea Ribichini