Graph drawing algorithms have important practical applications, e. g. layer-based algorithms for data ow diagram layout in embedded software design and planarization-based algorithms to layout UML diagrams in software engineering. Most current drawing methods focus on the optimization of aesthetic criteria such as the number of edge crossings and bends. The aspects of compactness and aspect ratio are often treated with lower priority, but in practice these are important as well. We present computational experiments showing that compactness can become a problem, especially for large and nested diagrams. Furthermore, we discuss possible new research directions.
In the context of graph-based diagrams, automatic layout algorithms are a
common tool to free developers from the time-consuming task of manually arranging
nodes and links on a canvas. Di erent kinds of diagrams may have
domain-speci c requirements on the arrangement of the elements. For data ow diagrams,
layer-based methods have proven themselves to work well [
With diagrams used in practice, however, we found that the drawings created
with these methods often lack compactness. Consider Fig. 1, a data ow diagram
from an industrial application [
Contributions. In this paper, we review existing research on the compactness of graph drawings, present results of experimental evaluations with practical diagrams, and discuss new ideas for future research. Summarizing the results of our experiments, we made the following observations: (O1) Aspect Ratio. Layer-based algorithms yield bad aspect ratios for certain diagrams, especially for diagrams with long directed paths. (O2) Whitespace of Compound Diagrams. For diagrams containing compound nodes, i. e. nodes that contain nested subgraphs, the amount of whitespace increases with the number of compound nodes when using layer-based algorithms. (O3) Whitespace and Planarization Methods. While planarization-based methods produce drawings with few edge crossings, for certain diagrams the amount of whitespace can increase drastically.
Outline. We de ne di erent aspects of compactness in Sect. 2 and discuss existing work on improving the compactness of diagrams in Sect. 3. Sect. 4 presents two experiments that quantify the fraction of diagrams that lack certain criteria of compactness. We conclude with possible future research directions in Sect. 5. 2
We de ne the width w of a diagram as the di erence between the largest and the smallest x-coordinate of any element in the drawing; the height h is de ned analogously using y-coordinates. Traditionally, compactness has been understood as the goal to minimize the area w h, or to minimize w or h independently (cf. the optimization goals for orthogonal compaction discussed in [15, Chapter 4]). Producer
Ramp2
LongToDouble
Ramp
Expression in/1000
XYPlotter randonTime2t1
VariableSleep
FrontDropQueue
Consumer Counter
Dropped
A di culty with this de nition is that it does not allow an absolute rating of a drawing, since it is not known how much area is required for a good drawing of a particular graph. Here we consider two other aspects of compactness that are easier to assess, namely the aspect ratio and the whitespace ratio. Aspect ratio. The aspect ratio of a drawing is r = w=h. An ideal aspect ratio matches the used display medium. For monitors this depends on the resolution, and is typically between 1:33 and 1:78. Often diagrams are printed to a sheet of paper, which has an aspect ratio of 1:41 (ISO 216 format). As drawings with aspect ratios outside, yet close to, these values are ne, we assume in the following that all aspect ratios r in the range 1 r 2 are acceptable.
Whitespace. The whitespace of a drawing is the area that remains unused. We measure the whitespace by literally painting the rectangular bounding box of all nodes onto a black-and-white canvas. Every node's bounding box includes possible labels and ports that are located outside the actual node. Additionally, layout algorithms can be con gured with a parameter s controlling the minimal spacing between any two nodes. We extend the bounding box in all directions by the value s. The whitespace value is the ratio of the number of pixels that are left white to the total number of pixels in the canvas.
Edges are neglected as we feel that including them in the black-and-white drawing would bias the result: long edges would lead to larger areas that are drawn in black and thus reduce the whitespace, contradicting the aesthetic criterion of minimizing edge length. For a similar reason, we omit compound nodes in the whitespace evaluation, since their size is adapted to the bounding box of their nested subgraph.
We are not aware of any studies evaluating how much whitespace is necessary or helpful to conceive a diagram optimally. Certainly some whitespace is necessary in order to emphasize certain structures such as grouping of nodes. In the future a quanti cation would be desirable. Furthermore, our results encourage a metric that takes more factors into account, such as edges. Following our de nition, graphs with higher edge density typically yield higher amounts of whitespace, hence the comparison of results for di erent graphs is problematic. 3
Layer-based algorithms. Layer-based methods are the standard approach for drawing directed graphs. It consists of the following steps: 1. Cycle removal: Eliminate cycles by reversing a small subset of edges. 2. Layer assignment: Assign all nodes to layers such that edges point from layers of lower index to layers of higher index. 3. Crossing reduction: Find an ordering of the nodes in each layer with the aim of reducing the overall number of crossings. 4. Coordinate assignment: Determine node coordinates and replace dummy nodes by bend points.
A very common optimization goal for layer assignment is to minimize the
sum of layer di erences of source and target nodes for all edges. While this can
be solved e ciently [
Planarization-based algorithms. The topology-shape-metrics approach consists of the following three phases: 1. Planarization: Remove edges until the graph is planar, then reinsert each removed edge with a minimal number of crossings. 2. Orthogonalization: Compute a bend-minimal edge routing that consists of horizontal and vertical line segments. 3. Compaction: Find a valid assignment of node and bend point coordinates such that the total length of line segments is minimized.
The simplest approach for one-dimensional compaction is based on longest
paths and guarantees a minimal width or height of the drawing, but does not
guarantee that the sum of the edge lengths is minimal. The latter can be achieved
using ow-based compaction. However, both methods require that the
orthogonal representation has only rectangular faces; this can be achieved by adding
additional edges (dissection) but limits the amount of freedom for compaction.
An alternative approach is based on turn-regularity [
Ptolemy data ow diagrams. Ptolemy is an open source project that ships with a number of example data ow models for testing and demonstration.3 The diagrams can be nested with compound actors, which are composed of further actors to describe subsystems; see Fig. 2 for an example where the Producer compound actor is expanded, i. e. its internals are made visible, and the Consumer compound actor is collapsed. All other actors are atomic actors, i. e. do not contain children.
For our evaluations we use three variations of these models. First, we atten all compound actors, i. e. all contained atomic actors are recursively moved to the highest hierarchy level and the compound actors are eliminated. Second, we display all atomic actors within their parent compound actors. Third, we start with collapsed compound actors and successively expand them, obtaining di erent views for each diagram. To illustrate this, Fig. 2 shows one expanded compound actor, Producer. Expanding the Consumer actor would yield another view where the content of both compound actors is visible. Overall we evaluated 330 attened diagrams, 199 diagrams with full hierarchy containing at least 2 compound nodes, and 11 successively expanded diagrams.
Class diagrams. KIELER is an open source project written in Java with over
1.4 million lines of code.4 We created eight class diagrams of several subprojects,
e. g. KIML, KLighD, and SCL. The diagrams contain 20 to 55 nodes and 27 to
75 edges. We use two variations of the class diagrams, one where the details of
classes and interfaces are visible and one where they are hidden, see Fig. 3.
North graphs (a. k. a. AT&T graphs). The library is widely used in the graph
drawing community and serves as an application-independent benchmark [
We processed the North graphs with the Dot algorithm of the Graphviz
library [
Results (O1) Aspect ratio. Table 1 gives an overview of the resulting aspect ratios of drawn diagrams; it can be seen that for every class of graphs less than 50 % of the drawings have an acceptable aspect ratio.
The results for the attened Ptolemy graphs and the North graphs are also shown in more detail in Fig. 4. Each bar accumulates the number of graphs with an aspect ratio within an interval of size 0:5, speci ed by the values left and right of the respective bar. The four marked bars depict the desired interval 1 r 2 of the aspect ratio r, and the right-most interval contains all graphs with r > 9:5. Only about 36 % (Ptolemy graphs) and 30 % (North graphs) have an aspect ratio in the desired interval. While the drawings with aspect ratio below 1 (presuming left-to-right layout) can be improved with alternative layer assignment methods discussed in Sect. 3, no current methods can handle the remaining 40 % and 18 % with an aspect ratio above 2 because the minimal number of layers is determined by the longest paths of these graphs (see Sect. 5).
30 % 25 % 20 % 15 % 10 % 5 % 0 %
0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0 5.5 6.0 6.5 7.0 7.5 8.0 8.5 9.0 9.5 (O2) Whitespace of compound diagrams. Table 2 shows the average amount of whitespace of the successively expanded Ptolemy diagrams. It can be seen that the amount of whitespace grows continuously with an increasing number of expanded compound nodes. Diagrams with more than nine compound nodes reach up to 97 % whitespace. Better methods have to be found to reduce the unused space for diagrams containing compound nodes (such as in Fig. 1). (O3) Whitespace and planarization methods. The amount of whitespace of the eight class diagrams after applying the planarization-based layout can be seen in Table 3. The same average value of about 72 % can be observed for both types of diagrams, the ones with hidden and with visible details. We found that the speci ed spacing around nodes has no signi cant impact on the relative amount of whitespace. The results in Table 3 originate from a spacing value of 50. Spacing values of 20 or 90 yield similar whitespace ratios of 70 73 %.
We applied the force-based FDP algorithm of Graphviz in addition to the
planarization-based method for a comparison. The algorithm was con gured to
produce drawings as compact as possible while remaining legible. This setup
yields 18 % whitespace on average. While we believe that the
planarizationbased drawings are more comprehensible because they produce fewer crossings,
we conclude that there are layout algorithms producing drawings with less than
a third of the whitespace when relaxing the goal to minimize edge crossings. In
terms of area, the examined class diagrams require an average of 5.3 monitors
when using planarization-based method, whereas all but three diagrams would
t on a single monitor using force-directed methods (0:7 on average).
We present four directions for future research: minimization of longest paths and
improved layer assignment for the layer based approach, and partial
orthogonalization and graph decomposition for the topology-shape-metrics approach.
1. Longest paths. The minimal number of layers for an acyclic graph is
determined by its longest path, since all nodes of a path have to be assigned to
di erent layers. Hence the longest path limits the freedom of layer assignment
algorithms regarding their goal of nding a layering that allows a compact
drawing. This fact has been neglected in previous approaches to cycle elimination,
which only address the number of reversed edges [
An important question is how to balance the two optimization goals. Ideally, this balancing should be controllable with a parameter, allowing to adapt the drawings to the needs of individual applications.
A possible heuristic for the generalized edge reversal problem is to separate
the two goals: rst make the graph acyclic using a standard method [
{ Edge removal during planarization. Edges with many crossings introduce
many dummy nodes, potentially increasing the size of the drawing. Instead
of inserting such edges during planarization, they could be removed.
{ Edge removal during orthogonalization. Edges with many bend points require
additional space in the compaction phase. A possible heuristic is to compute
an orthogonal representation, remove edges with too many bend points, and
then repeat the process iteratively.
4. Graph decomposition. Decomposing graphs and processing the components
with force-based drawing methods is known from multi-level approaches [
{ Trees. We remove subgraphs which are free trees from the input graph, so we get one core graph plus a collection of tree subgraphs. There are many options for drawing trees, and this freedom can be exploited to optimize compactness, e. g. the face into which to embed a tree can be freely chosen. { Biconnected components. Another possibility is to use the decomposition of the graph into its biconnected components. We can use a similar approach as for trees, identifying a large core graph and cutting out some subgraphs which are only connected at cut vertices. A more complex variant would be to use this approach recursively, i. e. for each removed subgraph we can again cut out subgraphs connected at cut vertices.