TopFish - A Viewer for Very Large Graphs

Yehuda Koren, Emden Gansner, Stephen North

Internet router graph (full)	Internet graph (zoomed in TopFish)

BGP graph (random)	BGP graph (majorization)	BGP graph (zoomed in TopFish)

Interactively viewing very large graphs is a key problem in information visualization. Often raw data has hundreds, thousands, even millions of objects. At the low end of that range, just making a readable layout that can be examined with pan-and-zoom and text search controls is challenging. At the high end, though, it simply is impossible to see that many distinct inividual objects simultaneously; in some way the data must be reduced in size, either before or after layout. The question is how to do this in an intuitive way that complements interactive data exploration, and runs quickly at full scale.

Yehuda Koren, Emden Gansner and Stephen North developed a novel large graph viewer called TopFish. TopFish assumes that a basic full layout is made externally. (This is a separate problem for which practical methods are available.) When TopFish loads the full layout, if it is large, nodes are usually overplotted and hard to distinguish. The TopFish solution is to allow a data analyst to set one or more focus points in the layout. TopFish then shows a very detailed view near a focus, and a simplified, but structurally correct view of the graph further away. The simplified view involves collapsing nodes that are topologically and geometrically close, reducing visual clutter. The foci may be moved interactively. When this is done, some nodes are expanded to show a higher level of detail, while others are collapsed as they become less visually important. Also, the layout is warped radially around foci to achieve more uniform density, making the diagram easier to read. TopFish computes views quickly, supporting high-interaction exploration of graphs much too large to explore as flat structures.