Department of Computer Science
Providence, RI 02912-1910
The visualization of conceptual structures is a key component of support tools for complex applications in science and engineering. Foremost among the visual representations used are drawings of graphs and ordered sets. In this talk, we survey recent advances in the theory and practice of graph drawing. Specific topics include bounds and tradeoffs for drawing properties, three-dimensional representations, methods for constraint satisfaction, and experimental studies.
In this paper, we survey selected research trends in graph drawing, and overview some recent results of the author and his collaborators.
Graph drawing addresses the problem of constructing geometric representations of graphs, a key component of support tools for complex applications in science and engineering. Graph drawing is a young research field that has growth very rapidly in the last decade. One of its distinctive characteristics is to have furthered collaborative efforts between computer scientists, mathematicians, and applied researchers.
A comprehensive bibliography on graph drawing algorithms  cites more than 300 papers written before 1993. Most papers on graph drawing are cited in geom.bib, the computational geometry BibTeX bibliography available from ftp://cs.usask.ca/pub/geometry/ (search for keyword ``graph drawing''). Surveys on various aspects of graph drawing appear in [24, 32, 41, 44, 74, 75, 78, 82, 83].
The proceedings of the annual Symposium on Graph Drawing are published by Springer-Verlag in the LNCS series [88, 5]. Three special issues of journals dedicated to graph drawing have been recently assembled [14, 26, 25]. Additional special issues are planned for future Graph Drawing Symposia.
The author maintains a WWW page (http://www.cs.brown.edu/people/rt/gd.html) with pointers to graph drawing resources on the Web.
The rest of this paper is organized as follows: Section 3 overviews lower an upper bounds on fundamental drawing properties, such as area, and gives tradeoffs between them. Basic graph drawing terminology is reviewed in Section 2. Three-dimensional drawings are discussed in Section 4. Section 5 deals with methods for constraint satisfaction. Finally, experimental studies are reported in Section 6.
First, we define some terminology on graphs pertinent to graph drawing:
In a drawing of a graph, vertices are represented by points (or by geometric figures such as circles or rectangles) and edges are represented by curves such that any two edges intersect at most in a finite number of points. Except for Section 4, which covers three-dimensional drawings, we consider drawings in the plane. The following types of drawings are defined:
Figure 1: Types of drawings: (a) polyline drawing of ; (b) straight-line drawing of ; (c) orthogonal drawing of ; (d) planar upward drawing of an acyclic digraph.
Straight-line and orthogonal drawings are special cases of polyline drawings. Polyline drawings provide great flexibility since they can approximate drawings with curved edges. However, edges with more than two or three bends may be difficult to ``follow'' for the eye. Also, a system that supports editing of polyline drawings is more complicated than one limited to straight-line drawings. Hence, depending on the application, polyline or straight-line drawings may be preferred. If vertices are represented by points, orthogonal drawings exist only for graphs of maximum vertex degree 4.
For various classes of graphs and drawing types, many universal/existential upper and lower bounds for specific drawing properties have been discovered. Such bounds typically exhibit trade-offs between drawing properties. A universal bound applies to all the graphs of a given class. An existential bound applies to infinitely many graphs of the class.
Whenever we give bounds on the area or edge length, we assume that the drawing is constrained by some resolution rule that prevents it from being arbitrarily scaled down (e.g., requiring a grid drawing, or a minimum unit distance between any two vertices).
Table 1 summarizes selected universal upper bounds and existential lower bounds on the area of drawings of graphs.
Class of Graphs Drawing Type
rooted tree upward planar straight-line grid
rooted tree strictly upward planar straight-line grid
tree upward planar polyline grid
binary tree upward planar orthogonal grid
tree planar straight-line grid
degree- tree planar polyline grid
degree-4 tree planar orthogonal grid
planar graph planar polyline grid
[27, 28, 56]
planar graph planar straight-line
planar graph planar straight-line grid
graph planar straight-line convex grid
planar graph planar orthogonal grid
[3, 56, 81, 86]
planar degree-4 graph orthogonal grid
[93, 60, 2]
upward planar digraph upward planar grid straight-line
[1, 28, 39]
reduced planar st-digraph upward planar grid straight-line dominance
upward planar digraph upward planar grid polyline
general graph polyline grid
In general, the effect of bends on the area requirement is dual. On one hand, bends occupy space and hence negatively affect the area. On the other hand, bends may help in routing edges without using additional space.
The following comments apply to Table 1. Linear or almost-linear bounds on the area can be achieved for trees. See Table 4 for trade-offs between area and aspect-ratio in drawings of trees. Planar graphs admit planar drawings with quadratic area. However, the area requirement of planar straight-line drawings may be exponential if high angular resolution is also desired. Almost linear area can be instead achieved in nonplanar drawings of planar graphs, which have applications to VLSI circuits. Upward planar drawings provide an interesting trade-off between area and the total number of bends. Indeed, unless the digraph is reduced, the area can become exponential if a straight-line drawing is required. A quadratic area bound is achieved only at the expense of a linear number of bends.
Tabe 2 summarizes selected universal lower bounds and existential upper bounds on the angular resolution of drawings of graphs.
|Class of Graphs||Drawing Type||Angular Resolution||Ref.|
|planar graph||planar straight-line||[40, 65]|
Table 3 summarizes selected universal upper bounds and existential lower bounds on the total and maximum number of bends in orthogonal drawings. Some bounds are stated for or because the maximum number of bends is at least 2 for and at least 3 for the skeleton graph of an octahedron, in any planar orthogonal drawing
|Class of Graphs||Drawing Type||Total No. Bends||Max No. Bends||Ref.|
|planar degree-4 graph||orthogonal planar||[3, 89]|
|embedded degree-4 graph||orthogonal planar||[34, 64, 86, 89]|
|biconnected embedded degree-4 graph||orthogonal planar||[34, 64, 86, 89]|
|triconnected embedded degree-4 graph||orthogonal planar|||
|embedded degree-3 graph||orthogonal planar||[56, 63]|
The ability to construct area-efficient drawings is essential in practical visualization applications, where screen space is at a premium. However, achieving small area is not enough: e.g., it is easy to see that a drawing with high aspect-ratio may not be conveniently placed on a workstation screen, even if it has modest area. Hence, it is important to keep the aspect-ratio small. Ideally, one would like to obtain small area for any given aspect-ratio in a wide range. This would provide graphical user interfaces with the flexibility of fitting drawings in arbitrarily shaped windows.
A variety of trade-offs for the area and aspect-ratio arise even when drawing graphs with a simple structure, such as trees. Table 4 summarizes selected universal bounds that can be simultaneously achieved on the area and the aspect-ratio of various types of drawings of trees.
|Class of Graphs||Drawing Type||Area||Aspect-Ratio||Ref.|
|rooted tree||upward planar straight-line layered grid||O(1)|||
|rooted tree||upward planar straight-line grid||[12, 79]|
|rooted degree-O(1) tree||upward planar polyline grid||O(n)|||
|binary tree||upward planar orthogonal grid|||
|degree-4 tree||orthogonal grid||O(n)||O(1)||[93, 60]|
|degree-4 tree||orthogonal grid, leaves on convex hull||O(1)|||
While upward planar straight-line drawings are the most natural way of visualizing rooted trees, the existing drawing techniques are unsatisfactory with respect to either the area requirement or the aspect ratio. The situation is similar for orthogonal drawings. Regarding polyline drawings, linear area can be achieved with a prescribed aspect ratio . However, experiments show that this is done at the expense of a somehow aesthetically unappealing drawing.
For non-upward drawings of trees, linear area and optimal aspect ratio are possible for planar orthogonal drawings, and a small (logarithmic) amount of extra area is needed if the leaves are constrained to be on the convex hull of the drawing (e.g., pins on the boundary of a VLSI circuit). However, the non-upward drawing methods do not seem to yield aesthetically pleasing drawings, and are suited more for VLSI layout than for visualization applications.
Table 5 summarizes selected universal bounds that can be simultaneously achieved on the area and the angular resolution of drawings of graphs.
|Class of Graphs||Drawing Type||Area||Angular Resolution||Ref.|
|planar graph||planar straight-line grid||[19, 77]|
|planar graph||planar straight-line|||
|planar graph||planar polyline grid|||
Universal lower bounds on the angular resolution exist that depend only on the degree of the graph. Also, substantially better bounds can be achieved by drawing a planar graph with bends or in a nonplanar way.
Recent advances in hardware and software technology for computer graphics open the possibility of displaying three-dimensional (3D) visualizations on a variety of low-cost workstations, and a handful of researchers (and film makers) have begun to explore the possibilities of displaying graphs using this new technology Previous research on 3D graph drawing has focused on the development of visualization systems (see, e.g., [73, 76]). Much work needs to be done on the theoretical foundations of 3D graph drawing. Recent progress has been reported in [8, 9, 33, 43, 51, 62].
A 3D convex drawing of a graph G is a realization of G by the skeleton of a 3D convex polytope (see Fig. 2. The well-known Steinitz's theorem says that a graph admits a 3D convex drawing if and only if it is planar and triconnected  (see also Grünbaum ), properties that can be verified in linear time (see, e.g., [48, 49]). Interestingly, it is a simple exercise to derive from the published proofs of Steinitz's theorem a cubic-time method for constructing 3D convex drawings in the real-RAM model . Unfortunately, this approach seems to require at least exponential volume and an exponential number of bits to implement. Indeed, Onn and Sturmfels  show how to construct a 3D convex grid drawing within a cube of side .
Figure 2: Example of a 3D convex drawing.
Maxwell  (see also [10, 11, 94]) describes a mapping that transforms a 2D convex drawings with a certain ``equilibrium stress property'' into a 3D convex drawing. Further results on this transformation are given by Hopcroft and Kahn . Eades and Garvan  show how to construct 3D convex drawings by combining the above transformation with the 2D-drawing method of Tutte [91, 92]. They also show that their drawings have exponential volume in the worst case. Smith (see ) claims a polynomial-time algorithm for constructing a 3D convex drawing inscribed in a sphere, with vertex coordinates represented by -bit numbers, for an n-vertex graph known to be inscribable (which can be tested in linear time, e.g., for planar triangulations, due to a result of Dillencourt and Smith ). Das and Goodrich  present a linear-time algorithm for constructing a 3D convex drawing of a maximal planar graph such that the vertex coordinates are rational numbers that can be represented with a polynomial number of bits.
Chrobak, Goodrich and Tamassia  have recently shown how to construct in time a 3D convex drawing with O(n) volume such that the vertex coordinates are represented by -bit rational numbers and any two vertices are at distance at least one.
Research in graph drawing has traditionally focused on algorithmic methods, where the drawing of the graph is generated according to a prespecified set of aesthetic criteria (such as planarity or area minimization) that are embodied in an algorithm. Although the algorithmic approach is computationally efficient, it does not naturally support constraints, i.e., requirements that the user may want to impose on the drawing of a specific graph (e.g., clustering or aligning a given set of vertices). Previous work has shown that only a rather limited constraint satisfaction capability can be added to existing drawing algorithms (see, e.g., [29, 84]).
Recently, several attempts have been made at developing languages for the specification of constraints and at devising techniques for graph drawing based on the resolution of systems of constraints (see, e.g., [20, 55, 66]). Eades and Lin  attempt at combining algorithmic and declarative methods in drawings of trees. Brandenburg presents a comprehensive approach to graph drawing based on graph grammars .
A visual approach to graph drawing, where the layout of a graph is pictorially specified ``by example,'' is proposed by Cruz, Garg and Tamassia [15, 16]. Within this approach, a graph is stored in an object-oriented database, and its drawing is defined used recursive visual rules of the visual meta-language DOODLE . The following types of drawings can be visually expressed in such a way that the system of constraints obtained from the application of the visual rules to the input graph can be solved in linear time:
Figure 3: Drawings of a planar st-digraph: (a) tessellation drawing; (b) visibility drawing; (c) upward polyline drawing.
In the rest of this section, we present visual programs for drawing a planar st-digraph, i.e., an embedded planar acyclic digraph with exactly one source and one sink, joined by an edge. Such digraphs play an important role in the theory of ordered sets since their transitive reductions are the covering digraphs of planar lattices . Such visual programs can be easily modified to construct drawings of upward planar digraphs, which are known to be subgraphs of planar st-digraphs [58, 27].
We show in Figure 4 a complete visual program for tessellation representations. We assume that the vertices, edges, and faces of the input planar st-digraph G are database objects, where for each object o the following attributes describing the embedding are stored: left face , right face , bottom vertex , and top vertex . Note that the value of each attribute is another database object.
Figure 4: Visual rules for constucting a tessellation drawing of a planar st-digraph: (a) rule for a face; (b) special rule for the source vertex; (c) rule for a vertex; (d) rule for an edge.
Each rule defines the visual representation of a database object of a certain class (vertex, edge, and face). For tessellation representations, this is a horizontal segment for a vertex, a vertical segment for a face, and a rectangle for an edge. The visual notation in the rule for an object o includes:
Complete visual programs for visibility representations and upward polyline drawings are shown in Figures 5 and 6, respectively. In these two programs, the visual representation of the faces is a single point associated with landmark F. This point is invisible but contributes to the definition of the constraints. Also, the visual representation of an edge includes a visible portion (vertical segment for a visibility representation and polygonal chain with three segments for an upward polyline drawing) and an invisible portion drawn with a conventional ``transparent color'' (a rectangle or segment with shaded lines in the figures).
Figure 5: Visual rules for constucting a tessellation drawing of a planar st-digraph: (a) rule for a face; (b) special rule for the source vertex; (c) rule for a vertex; (d) rule for an edge.
Figure 6: Visual rules for constucting a tessellation drawing of a planar st-digraph: (a) rule for a face; (b) special rule for the source vertex; (c) rule for a vertex; (d) rule for an edge.
Many graph drawing algorithms have been implemented and used in practical applications. Most papers show sample outputs, and some also provide limited experimental results on small test suites (see, e.g., [18, 36, 37, 53, 55, 57] and the experimental papers in ). However, in order to evaluate the practical performance of a graph drawing algorithm in visualization applications, it is essential to perform extensive experimentations with input graphs derived from the application domain.
The performance of four planar straight-line drawing algorithms on 10,000 randomly generated maximal planar graphs is compared by Jones et al. .
Himsolt  presents a comparative study of twelve graph drawings algorithms based on various approaches. The experiments are conducted on 100 sample graphs with the graph drawing system GraphEd . Many examples of drawings constructed by the algorithms are shown, and various objective and subjective evaluations on the aesthetic quality of the drawings produced are given.
Brandenburg and Rohrer  compare five ``force-directed'' methods for constructing straight-line drawings of general undirected graphs. The algorithms are tested on a a wide collection of examples and with different settings of the force parameters. The quality measures evaluated are crossings, edge length, vertex distribution, and running time. They also identify tradeoffs between the running time and the aesthetic quality of the drawings produced.
Jünger and Mutzel  investigate crossing minimization strategies for straight-line drawings of 2-layer graphs, and compare the performance of eight popular heuristics for this problem.
In [22, 23] Di Battista et al. present an extensive experimental study comparing four general-purpose graph drawing algorithms. The four algorithms, denoted Bend-Stretch, Column, Giotto, and Pair, take as input general graphs (with no restrictions whatsoever on the connectivity, planarity, etc.) and construct orthogonal grid drawings, which are widely used in software and database visualization applications.
Algorithms Bend-Stretch and Giotto are based on a general approach where the drawing is incrementally specified in three phases: The first phase, planarization, determines the topology of the drawing. The second phase, orthogonalization, computes an orthogonal shape for the drawing. The third phase, compaction, produces the final drawing. This approach allows homogeneous treatment of a wide range of diagrammatic representations, aesthetics and constraints (see, e.g., [57, 84, 90]) and has been successfully used in industrial tools. The main difference between the two algorithms is in the orthogonalization phase: Algorithm Giotto uses a network-flow method that guarantees the minimum number of bends but has quadratic time-complexity . Algorithm Bend-Stretch adopts the ``bend-stretching'' heuristic  that only guarantees a constant number of bends on each edge but runs in linear time.
Algorithm Column is an extension of the orthogonal drawing algorithm by Biedl and Kant  to graphs of arbitrary vertex degree. The orthogonal grid drawing is incrementally constructed by adding the vertices one at a time. Namely, at each step a vertex v is added plus the edges connecting v to previously added vertices. Some columns of the grid are ``reserved'' to draw the remaining incident edges of v. Concerning the position of v, since one row is used for each vertex, the y-coordinate is immediately given by the order of visit of v, and the x-coordinate is the one of the reserved column of the incident edge of v that minimizes the number of bends introduced by the new edges. Algorithm Pair is an extension of the orthogonal drawing algorithm by Papakostas and Tollis [69, 70] to graphs of arbitrary vertex degree.
Examples of ``typical'' drawings generated by Bend-Stretch, Column, Giotto, and Pair are shown in Figures 7.
Figure 7: Drawings of the same 63-vertex graph produced by algorithms
(a) Bend-Stretch, (b) Giotto, (c) Column,
and (d) Pair, respectively.
The test data (available on the Internet) are 11,582 graphs, ranging from 10 to 100 vertices, generated from a core set of 112 graphs used in ``real-life'' software engineering and database applications. The experiments provide a detailed quantitative evaluation of the performance of the four algorithms and show that they exhibit trade-offs between ``aesthetic'' properties (e.g., crossings, bends, edge length) and running time. For example, Fig. 8 shows the average area number of crossings, and CPU time. The observed practical behavior of the algorithms is consistent with their theoretical properties. Namely, Giotto outperforms the other algorithms for most quality measures but is considerably slower than Column and Pair.
Figure 8: (a) Average area versus number of vertices. (b) Average number of crossings versus number of vertices. (c) Average CPU time (seconds) versus number of vertices.
Advances in the Theory and
Practice of Graph Drawing
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 ordal96.tex.
The translation was initiated by Roberto Tamassia on Thu Aug 1 13:38:15 EDT 1996