Space-approximation Trade-off
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