Visualization of Large Graph

Stephen Kobourov, Johns Hopkins University

Visualization of relational information is an important problem in many areas of computer science, including VLSI design, networks, and telecommunications. Visualization of large graphs is particularly difficult given the constraints imposed by the current technology (limited number of pixels on a screen) and the complexity of the graphs to be displayed (millions of nodes and edges). We consider efficient techniques for displaying large graphs based on the hierarchical decomposition approach: the graph is decomposed into a logarithmic number of layers, such that each layer represents the graph in more detail. Using such a recursive clustering scheme, the graph can be displayed in 3 dimensions to convey its global structure; at the same time, clusters can be displayed alongside the hierarchy to show the local structure in an area of interest. We also develop cluster-based algorithms for drawing large planar graphs such that planarity and c-planarity (a stronger condition for planarity of planar graphs) are maintained. These algorithms are space and time efficient and optimize various aesthetic criteria to enhance the quality of the resulting drawings.