Information Visualization is an emerging field that focuses on presenting (typically non-spatial) information in a visual form to help in interpreting and understanding it [9, 61].
Graph Visualization (also known as Graph Drawing) is a sub-field of Information Visualization that focuses on constructing visual representations of graphs. A graph is a data structure consisting of a set of vertices and a set of edges connecting these vertices. Graphs are ubiquitous structures in computer science and are used to model information in a variety of applications including Geographic Information Systems, Computer Aided Design, Geometric Modeling, Network Design, Software Engineering, Web Navigation, Multimedia Document Authoring, VLSI Design, and Program Debugging. A visual representation of a graph can not only be helpful in understanding its structure, but can also be used to carry out useful operations in the task-domain. For example, during a Web-browsing session, we can display a ``history graph'' on screen that shows the sites visited by the user and the links between them [35, 54, 58]. This visual representation not only prevents the user from ``getting lost'' in the Web space but also using it she can edit the history graph directly, or can even explore the Web by clicking on a site to go there or to show sites linked to it [35].
Graphs are generally visualized using node-link diagrams where vertices are usually drawn as rectangles, boxes, circles, or spheres, and edges are usually drawn as polyline-segments, curves, or tubes. A (graph) visualization can be more effective in presenting information if it has certain aesthetic properties [17] such as few edge bends and few edge crossings, efficient use of screen space, large angular separation between edges, small edge-lengths, and adherence to application-specific restrictions such as centering and clustering [46]. The use of well-established technologies such as fisheye views [28, 63], direct manipulation [38, 64], dynamic queries [1, 65, 75], zooming [2], hierarchical decomposition [26, 36, 50], and multiple views [50] in a visualization further enhances its effectiveness.