We address graph visualization from the viewpoint of compiler construction. Drawings of compiler data structures such as syntax trees, control flow graphs, dependency graphs [WiMa95], are used for demonstration, debugging and documentation of compilers. In real world compiler applications, such drawings cannot be produced manually because the graphs are automatically generated, large, often dense, and seldom planar. Graph layout algorithms help to produce drawings automatically: they calculate positions of nodes and edges of the graph in the plane.
Our main focus is the animation and interactive exploration of compiler graphs. Thus, fast layout algorithms are required. Animations show the behaviour of an algorithm by a running sequence of drawings. Thus there is not much time to calculate a layout between two subsequent drawings. In interactive exploration, it is annoying if the user has to wait a long time for a layout. Here, a good layout quality is needed, but the speed of visualization is even more important. As long as the layout quality is good enough to comprehend the picture, the user may accept small aesthetic deficiencies of the drawing.
In contrast, consider graph visualization for textbook publishing. Here, typically pictures of small graphs are used to demonstrate idealized abstractions of facts. Such pictures are mostly produced by hand. Their quality must be optimal in order to make the facts very easily comprehensible for the reader of the textbook. If automatically calculated layout is used, the techniques are different from those in interactive visualization: The calculation time may range up to hours because the quality of the drawing is more important in textbook publishing.
Layout techniques for interactive graph exploration usually are iterative heuristics. Iterative algorithms allow to trade time for quality. If the layout quality is not satisfactory, more iterations are calculated, which is slower but gives better results. Heuristics are used because this allows to satisfy several potentially contradicting aesthetic requirements in a balanced way. General aesthetic layout criteria include minimization of edge crossings and node overlappings, display of symmetries, reduction of bend points in edges, uniform orientations of directed edges, and closeness of related nodes.
Apart from the layout heuristics, powerful browsing mechanisms are needed for interactive graph exploration. Many facilities such as unlimited scaling, searching of nodes, and following chains of edges are offered as a matter of course in today's graph drawing tools. Some advanced facilities are grouping nodes, collapsing groups into summary nodes (folding), hiding classes of nodes, and displaying special views onto the graph.
We present layout methods and browsing facilities suitable for graph visualization in compiler construction. After defining the general notation, the section 3 gives a survey of straight line drawing heuristics derived from physical models. Section 4 presents variants of a method for layered (hierarchical) layouts. Section 5 sketches some ideas about interactive grouping and folding of graphs, and section 6 presents browsing facilities with special views. Most of the mentioned algorithms and methods are implemented in the VCG tool, a graph layout tool designed for applications from compiler construction [Sa94]. All examples of this paper are generated by the VCG tool.
In a demonstration session, we intend to give a survey of the facilities of the VCG tool by showing some typical applications.