P.O. Box 830688, EC 31, Richardson, TX 75083-0688, USA
tollis@utdallas.edu, http://www.utdallas.edu/~tollis/
Abstract: The visualization of complex conceptual structures is a key component of support tools for many applications in science and engineering. Several information visualization problems involve drawing graphs so that they are easy to read and understand. More research is needed to better understand the intricacies of drawing a graph in two or three dimensions. In this paper (see also the full position paper) we give a short discussion of and links to previous achievements, and present some future challenges.Categories and Subject Descriptors: H.5.2 [INFORMATION INTERFACES AND PRESENTATION]: User Interfaces (User Interface Management Systems (UIMS) - Theory and Methods); I.3.5 [COMPUTER GRAPHICS]: Computational Geometry and Object Modeling (Geometric algorithms, languages, and systems); F.2.2 [ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY]: Nonnumerical Algorithms and Problems (Computations on discrete structures - Geometrical problems and computations);
General Terms: Algorithms, Design, Experimentation, Languages, Performance, Theory, Systems.
Additional Key Words and Phrases: Graph Drawing, Information Visualization, Computational Geometry, Software Tools.
1. A Picture is Worth a Thousand Words
The visualization of complex conceptual structures is a key component of support tools for many applications in science and engineering. Examples include software engineering (call graphs, class hierarchies), visual interfaces, database systems (entity-relationship diagrams), digital libraries and World Wide Web authoring and browsing (hypermedia documents), distributed computation (reachability graphs of communicating processes), VLSI (symbolic layout), electronic systems (block diagrams, circuit schematics), project management (PERT diagrams, organization charts), decision support (scheduling and logistic diagrams), medicine (concept lattices), telecommunications (ring covers of networks), and law (conceptual nets).
A graph is an abstract structure that is used to model information. Graphs may be used to represent any information that can be modeled as objects and connections between those objects. Therefore, almost every domain of computer science (and other fields of science and engineering) and hence most segments of the software industry use graphs in some form to represent information. In addition to the above areas, graphs are used to display information in applications for compilers, engineering and CAD, parallel architectures, information management, network and systems management, financial transaction management, Object Oriented Analysis/Design, modeling networks of chemical reactions, and many other applications.
Figure 1. A fragment of an airline database schema (courtesy of R. Tamassia).
Information visualization problems involve drawing graphs so that they are easy to read and understand. Graph Drawing and Visualization addresses the problem of constructing geometric representations of conceptual structures that are modeled by graphs, networks, or hypergraphs, and has many applications to key computer technologies as described above. Figure 1 represents a fragment of an airline database schema. The layout was automatically generated by the GIOTTO algorithm [Tamassia, Di Battista, Batini 1988] through the WWW-based Graph Drawing Server. Over the last ten years there has been significant growth in research in graph drawing theory, systems, and applications. The latest version of the Annotated Bibliography on Graph Drawing by Di Battista, Eades, Tamassia, and Tollis, contains more than 300 papers on graph drawing algorithms and systems [Di Battista et al. 1994].
In information visualization applications, the usefulness of a drawing of a graph depends on its readability, that is, the capability of conveying the meaning of the diagram quickly and clearly. Various graphic standards have been proposed for drawing graphs in the plane, depending on the application. Usually, the vertices are represented by circles or boxes, and the edges are represented by a simple open curve between the vertices. A straight-line drawing maps each edge into a straight-line segment. A drawing such that each edge is represented by a polygonal chain is a polyline drawing.
Readability issues are expressed by means of aesthetics, which can be formulated as optimization goals for the drawing algorithms. In general, the aesthetics depend on the graphic standard adopted and the particular class of graphs of interest. A fundamental and classical aesthetic is the minimization of crossings between edges. A drawing is planar if no two edges intersect. A drawing is a grid drawing if the vertices (and the bends) of the edges have integer coordinates. In grid drawings, the area of the smallest rectangle covering the drawing should be minimal. In all graphic standards, the display of symmetries is desirable. It should be noted that aesthetics are subjective and may need to be tailored to suit personal preferences, applications, traditions, and culture.
2. Issues in Graph Drawing and Visualization
Current research in graph drawing and visualization addresses both theoretical and applied issues. It is outside the scope of this paper to give a complete presentation of the various problems and algorithms of graph drawing. Therefore, we give some examples of standards and results. For a more complete treatment of the topic the interested reader is referred to [Di Battista et al. 1994]. Also, for a more recent compilation of results in excellent tabular exposition see [Tamassia 1997].
On the theoretical side researchers have investigated issues ranging from combinatorial properties of graphs to algorithms that produce drawings with provably good upper bounds on the area, number of bends, etc., to lower bounds. On the systems side, there are several graph drawing tools that have been presented in the recent Symposia on Graph Drawing ( [Tamassia Tollis 1995], [Brandenburg 1996], [North 1997],) and commercial graph drawing tools, such as the Graph Layout Toolkit (GLT) by Tom Sawyer Software, Inc.
2.1 Orthogonal Graph Drawing
An orthogonal drawing is a polyline drawing that
maps each edge into a chain of horizontal and vertical segments.
Database diagrams, software engineering case tools,
circuit layout, and many other applications use this standard.
An orthogonal drawing is shown in the following figure:
Figure 2. An orthogonal drawing produced by an interactive technique. The dotted rectangles denote the current drawing (before the next insertion) at all intermediate steps.
The problems of producing a planar orthogonal drawing of a planar graph with either (a) the minimum number of bends, or (b) minimum area, are NP-complete. However, Tamassia uses network flow techniques to give a polynomial-time algorithm for minimizing bends when the graph and a fixed embedding are given as input [Tamassia 1987]. Di Battista, Liotta, and Vargiu give polynomial time algorithms for minimizing bends (considering all the possible embeddings) for series-parallel graphs and planar graphs with degree at most 3 [Di Battista et al. 1993]. Lower bounds for planar orthogonal drawings of graphs are described in [Tamassia Tollis Vitter 1991]. On the other hand, a linear-time heuristic algorithm for bend minimization with performance guarantees is presented in [Tamassia Tollis 1989].
The problem of producing non-planar orthogonal drawings of graphs with small area and low number of bends has been investigated in [Biedl Kant 1994], [Papakostas Tollis 1994], and [Papakostas Tollis 1997]. An orthogonal library was implemented, and included for the first time in the Graph Layout Toolkit, version GLT 2.2. An extensive experimental study of four orthogonal drawing algorithms was performed and the results were reported in [Di Battista et al. 1994]. For more information on these and other recent results in graph drawing see [Tamassia 1997].
Typically, the drawing algorithm is given a graph as an input and it produces a drawing of this graph. If an insertion (or deletion) is performed on the graph, then we have a new graph. Running the drawing algorithm again will result in a new drawing, which might be vastly different from the previous one. This is an inefficient use of time and resources from two points of view: (a) the time to run the algorithm on the new graph, and (b) the user may have spent a significant amount of time in order to understand and analyze the previous drawing; the new drawing may be very different requiring additional time for understanding. The area of Interactive Graph Drawing is concerned with the investigation of techniques that run efficiently and introduce minimal changes to the current drawing, thus preserving the user mental map.
It is interesting to note that the drawing of Figure 2 was obtained using an interactive scenario. The vertices of the graph were inserted one at a time in the order shown by their number. During each insertion the previous drawing (shown enclosed in the dashed rectangles) remains completely unchanged. The details of this technique can be found in [Papakostas Tollis 1996].
In the following figure we show one more orthogonal drawing of the above graph which is also obtained interactively. In this case the general shape of the current drawing remains unchanged after an insertion is performed. However, several vertices and bends of the current drawing may shift by a total amount of at most 6 units along the x and y axes. The details of this technique along with experimental results comparing the two interactive techniques can be found in [Papakostas Six Tollis 1997].
Figure 3. An orthogonal drawing produced by another interactive technique.
2.2 Force Directed Graph Drawing
A straight-line drawing of a telecommunication network is shown in Figure 4.
This drawing was obtained using the symmetric library of
GLT 2.2 (by Tom Sawyer Software, Inc.). It is based on a simulation
of a physical model known as the spring embedder.
Spring embedder algorithms simulate a physical model where vertices and
edges represent various forces and the result is a drawing representing
a configuration of minimum energy.
Eades presented the first spring embedder in
[Eades 1984].
Since then several authors have presented variations of
the original technique.
The most recent techniques have appeared
in [Tamassia Tollis 1995],
[Brandenburg 1996], and
[North 1997].
Another technique that seems to produce nice drawings is simulated
annealing.
An important problem in the design of survivable telecommunication
networks is finding a small set of cycles that covers all nodes.
Notice that such a set is displayed very nicely in the above drawing.
In fact the strong point of these techniques is that the symmetries
of the graphs are displayed, and hence the drawings can be
useful in many stages of the design of a project.
However, these techniques typically take a long time to converge.
Figure 4. A drawing of a telecommunication network.
2.3 Hierarchical Graph Drawing
Typical polyline drawings are the hierarchical drawings (also
known as upward drawings).
These are drawings of directed acyclic graphs such that
each edge is a curve monotonically increasing
in some direction (edges flow in the same direction).
Such drawings are ideal for displaying hierarchies, in PERT diagrams, organization charts, scheduling and logistic diagrams, etc.
Figure 5 shows how the closure of the C function newEdge
(through reachability analysis) changes from one version to the other.
The drawing was generated by CIAO (courtesy of R. Chen, E.
Koutsofios, and S. North, AT&T Research Labs).
The first comprehensive approach to hierarchical drawings
was presented by [Sugiyama Tagawa Toda 1981].
In this approach the vertices and bends are constrained to lie
on a set of equally spaced horizontal lines, called layers.
Improved variations and extensions of this approach were presented
in [Gansner North Vo 1988] and
[Gansner et al. 1993].
Several researchers have investigated the problem of reducing
crossings between layers.
Figure 5. Reachability analysis of the C function newEdge (courtesy of R. Chen, E. Koutsofios, and S. North, AT&T Research Labs).
Another approach to hierarchical drawings is to first planarize the given graph (by replacing each crossing with a dummy vertex) and next to produce a planar upward drawing. It turns out that the problem of deciding whether a given planar directed acyclic graph admits an upward drawing is NP-complete [Garg Tamassia 1995]. However, for special classes of graphs, polynomial time algorithms have been found. For more information see [Di Battista et al. 1994] and [Tamassia 1997]. An experimental study of various algorithms for producing hierarchical drawings is presented in [Di Battista et al. 1997].
3. Open Problems
Despite the abundance of literature on graph drawing (see [Di Battista et al. 1994] and [Tamassia 1997]), many theoretical and practical problems are still open. A few of the most promising directions for further research are listed below.
- Better Techniques for Hierarchical Drawings.
- Better Techniques for Orthogonal Drawings.
- General Strategies for Straight-Line Drawings.
- General Strategies for Polyline Drawings.
- Label Placement for vertices and edges.
- Interactive Graph Drawing in Various Graphic Standards.
- Three dimensional Graph Drawing.
- Conceptual fisheye views for displaying large graphs.
Because of the trend of software (in becoming more user friendly) and the breadth of applications that require Graph Drawing and Visualization, the topic will become even more popular in the near future. Also, as can be seen from the proceedings of GD '94, GD '95, and GD '96, as well as the participants, there is a very good mix of theory and practice, and both theoreticians and practitioners are willing to talk and listen to each other.
We believe that the field of Graph Drawing and Visualization has many important applications in key computer technologies, and will become a central component of most user friendly software tools of the future. Hence it should be funded at high levels. Furthermore, the field is mature and should be funded by the National Science Foundation and other funding organizations within specific programs, as is the case with many other fields.