Navigating Giga-Graphs

James Abello, Jeffrey Korn, Matthias Kreuseler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


An effective way to process a graph that does not fit in RAM is to build a hierarchical partition of its set of vertices. This hierarchy induces a partition of the graph edge set. We use this partition to produce a macro view of the graph. A screen embedding of this macro view is a Graph Sketch. We describe the use of Rectangular FishEye Views to provide drill-down navigation of graph sketches at different levels of detail including the graph edges data. A higher level of detail of a sketch focus area is obtained by distorting the lower detail context. Alternative visual representations can be used at different sketch hierarchy levels. We provide two sketch screen embeddings. One is tree-map based and the other is obtained by a special sequence of graph edge contractions. We demonstrate the application of our current Unix/Windows prototype to telecommunication graphs with edge sets ranging from 100 million to 1 billion edges(Giga-Graphs). To our knowledge this is the first time that focus within context techniques have been used successfully for the navigation of external memory graphs.

Original languageEnglish (US)
Title of host publicationProceedings of the Working Conference on Advanced Visual Interfaces, AVI 2002
Number of pages10
StatePublished - 2002
Externally publishedYes
EventWorking Conference on Advanced Visual Interfaces, AVI 2002 - Trento, Italy
Duration: May 22 2002May 24 2002

Publication series

NameProceedings of the Workshop on Advanced Visual Interfaces AVI


ConferenceWorking Conference on Advanced Visual Interfaces, AVI 2002

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction


  • external memory algorithms
  • fisheye views
  • graph sketches
  • hierarchies
  • massive data sets
  • visualization


Dive into the research topics of 'Navigating Giga-Graphs'. Together they form a unique fingerprint.

Cite this