H. S. Teoh:
I'm hoping for a kind of compressed representation where multiple adjacent nodes can be represented in a very compact way, by somehow taking advantage of the fact that they lie on an n-dimensional grid and the fact that graph edges are always a subset of grid edges (as opposedto edges between two arbitrary nodes).
Look for Succinct Data-Structures, Graphs. You can impose further memory savings in your problem.
Bye, bearophile
