Visualization of Large Graphs

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.