IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-7, NO. 2, MARCH 1981

223

Tidier Drawings of TreesEDWARD M. REINGOLD AND JOHN S. TILFORD

Abstract-Various algorithms have been proposed for producing tidy
drawings of trees-drawings that are aesthetically pleasing and use minimum drawing space. We show that these algorithms contain somedifficulties that lead to aesthetically unpleasing, wider than necessary
drawings. We then present a new algorithm with comparable time andstorage requirements that produces tidier drawings. Generalizations
to forests and m-ary trees are discussed, as are some problems in discretization when alphanumeric output devices are used.
Index Terns-Data structures, trees, tree structures.

INTRODUCTION
IN a recent article [6], Wetherell and Shannon presented algo-rithms for producing "tidy" drawings of trees-drawings
that use as little space as possible while satisfying certain
aesthetics. The basic task is the assignment of x and y coordinates to each node of a tree, after which a straightforwardplotting or printing routine generates a drawing of the tree.
Wetherell and Shannon give three aesthetics in an attempt todefine a "tidy" drawing of a binary tree.
Aesthetic 1: Nodes at the same level of the tree should lie
along a straight line, and the straight lines defining the levels
should be parallel.
Aesthetic 2: A left son should be positioned to the left ofits father and a right son to the right.
Aesthetic 3: A father should be centered over its sons.
Although not mentioned in [6], Aesthetic 1 was also meant
to require that the relative order of nodes across any level be
the same as in the level order traversal of the tree. This can beshown to guarantee that edges in the tree do not intersect
except at nodes.
The algorithms presented in [6], try to achieve these aesthetics while at the same time minimizing width. Similar algorithms were developed by Sweet [3] for use in his thesis, butwere never published. The basic algorithm of [6] proceeds asfollows. First, store in each node its level in the tree; this isessentially its y coordinate. Then traverse the tree in postorder, pausing at each node to give it an x coordinate. Initially,a provisional x coordinate is assigned according to this rule: if
the node is a leaf, give it the next available position on its
level; if it has only a left son, give it a position one unit to theright of its son; if it has only a right son, give it a position one
unit to the left of its son; otherwise (the node has two sons)give it the average of their positions. Meanwhile, keep track
Manuscript received April 10, 1980.
The authors are with the Department of Computer Science, University of Illinois, Urbana-Champaign, IL 61801.

Fig. 1. Final positioning of example tree as drawn by Algorithm WS.

of the next available position on each level with an array
NEXT POS, indexed by level, in which each value is set to two
greater than the coordinate of the last node assigned on thecorresponding level.
If a provisional position is less than the next available position on that level, the node is given the next available position,and its subtrees are shifted to the right so as to be properly
positioned relative to it. Actually, the amount of the shift isjust stored in the current node and applied with all the othershifts during a subsequent preorder traversal. Whenever a shift
is applied to a node, all nonleaf nodes to its right on the samelevel must have at least the same shift applied to them andtheir subtrees (because the nodes in those subtrees were positioned without knowledge of shifts that would occur abovethem). This necessitates another array, indexed by level,
containing the most recent shift applied on each level.
DIFFICULTIES

Algorithm WS works well in many cases; however, it contains an important deficiency. It can produce drawings that are
not really pleasing and that can be made narrower within theconstraints of the aesthetics. In Fig. 1, for example, nodes Y
and Z are too far apart; instead, the tree ought to be drawn asshown in Fig. 2 because that tree is both narrower and aesthetically more pleasing, in fact, "tidier."
The problem of Algorithm WS in the drawing of Fig. 1 is theinfluence of the fixed left margin, defmed by the values of thearray NEXT _POS. Since node Y is a leaf, it receives the next
available position on its level, 6. Now the lower part of the0098-5589/81/0300-0223$00.75 © 1981 IEEE

224

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-7, NO. 2, MARCH 1981

Fig. 4. A tree and its mirror image positioned by Algorithm WS.

Fig. 2. Example tree as drawn by Algorithm TR.

Fig. 5. A tree for which the narrowest drawing that satisfies Aesthetics

1-3 violates Aesthetic 4. The subtrees rooted at P and Q are isomorphic, but must be drawn nonisomorphically (as shown) to obtaina minimum width drawing.

Fig. 3. Example tree drawn by a modified Algorithm WS.

right subtree is built as usual, with Z being placed at 12. X,
the father of Y and Z, is given the average of their positions,
i.e., 9, and V receives the average of the positions of W and X,
which is 8. This is too far to the left according to NEXT_POS,
so the subtree rooted at V is shifted two units to the right.
The resulting tree is two units wider than necessary. The
culprit is the empty space in the middle of the tree; it caused
Y to be placed too far to the left when it should have been
the minimum distance from Z (as A is from B). As the number of nodes increases, this anomalous behavior of Algorithm
WS can worsen.
Wetherell and Shannon present a modification to Algorithm
WS that guarantees minimum width drawings at the expense of
Aesthetic 3. Although the drawing it produces for the sample
tree (see Fig. 3) is not too wide, the drawing of Fig. 2 is muchbetter. Vaucher [5], independently of [3] and [6], developeda tree printing algorithm that seems to avoid this problem but
does not satisfy the additional aesthetic constraint introducedin the next section.
As our example illustrates, the difficulty with Algorithm WS

stems from the fact that the shape of a subtree is influenced
by the positioning of nodes outside that subtree; Sweet [3]made a similar observation. As a consequence, symmetrictrees may be drawn asymmetrically, or more generally, a tree
and its reflection will not always produce mirror image drawings; even the same subtree may appear differently in different
parts of the tree. Fig. 4 shows a small tree and its reflection
whose drawings by Algorithm WS are not mirror images.

A NEW AESTHETIC AND ALGORITHM
It is certainly desirable that a symmetric tree be drawn
symmetrically; therefore, we introduce a new aesthetic thatguarantees this (along with a somewhat stronger requirement).
Aesthetic 4: A tree and its mirror image should produce
drawings that are reflections of one another; moreover, a subtree should be drawn the same way regardless of where it
occurs in the tree.
We pay a price for this aesthetic in terms of the width of thetree. Fig. 5 illustrates a tree for which the narrowest drawingthat satisfies Aesthetics 1-3 violates Aesthetic 4. Nevertheless,we consider Aesthetic 4 to be more important than minimum
width since the shape of the printed tree and its reflection
ought to be independent of its surroundings to aid in humanperception. In any case, with the exception of the theoretically interesting but impractical linear programming techniqueof [2], the published tree printing algorithms all fail to produce minimum width placements, even without the strictureof Aesthetic 4.

225

REINGOLD AND TILFORD: TIDIER DRAWINGS OF TREES

Satisfying Aesthetic 4 requires an algorithm in which nodes
outside a subtree do not interfere with the relative positionings
of nodes in the subtree, so that the inherent asymmetry of the
postorder traversal will not be manifested in the drawing. To
this end we propose Algorithm TR, based on the following
heuristic: two subtrees of a node should be formed independently, and then placed as close together as possible. Byrequiring that the subtrees be rigid at the time they are put
together, we avoid the undesirable effects that can accrue frompositioning nodes rather than subtrees.
The above heuristic is applied during a postorder traversal asfollows. At each node T, imagine that its two subtrees havebeen drawn and cut out of paper along their contours. We
then superimpose the two subtrees at their roots and movethem apart until no two points are touching. Initially theirroots are separated by some agreed upon minimum distance;then at the next lower level, we push them apart until minimum separation is established there. This process continues
at successively lower levels until we get to the bottom of theshorter subtree. At some levels no movement may be necessary; but at no level are the two subtrees moved closer together. When the process is complete, we fix the position of
the subtrees relative to their father, which is centered overthem. Assured that the subtrees cannot be placed closer
together, we continue the postorder traversal. After thistraversal, a preorder traversal converts the relative positionings
into absolute coordinates.
This technique is similar to Algorithm WS in several ways:
Aesthetics 1, 2, and 3 are satisfied; fathers are visited aftersons so that they may be centered over them; and empty
subtrees are handled as in Algorithm WS. The essential difference is that mirror image trees produce mirror image drawings and a subtree is drawn identically wherever it occurs.
Although the idea behind Algorithm TR is simple, implementation is somewhat tricky, because we need an efficient
way to follow the contour of a subtree as it is compared to its
brother subtree. As Fig. 2 illustrates, simply following left andright links does not suffice. Note, however, that when thenext node on the contour is not a son of the current node, thecurrent node must be a leaf; in many applications this meansthat it contains two unused pointer fields. We can use oneof these fields to store a temporary pointer to the next nodeon the contour, as long as we reserve an additional bit todistinguish it from a regular pointer. This idea is reminiscentof threaded binary trees [11, and so we call these distinguishedpointers "threads." Fortunately, the maintenance of thesethreads is not difficult and can be done at the same time thesubtrees are positioned.
We have implemented Algorithm TR in Pascal; the bulk of
the work is,done by the recursive postorder traversal procedure shown in Fig. 6. During the traversal the procedure
performs three tasks at each node T: first it determines how
close together the subtrees of T can be placed; second, it
keeps track of nodes that may need to be threaded later; andthird, it inserts a thread if one is required.
Since Aesthetic 3 requires that fathers be centered over sons,it suffices to include a single integer field in each node thatspecifies the horizontal offset between the node and each of

PROCEDURE SETUP ( T: LENK;LEVEL: INTEGER;
VAR REOST,LMOST EXTREME );(* ROOT OF SUBTREE(* CURRENT OVERALL LEVEL(k EXTREME DESCENDANTS(* THIS PROCEDURE IMPLEMENTS ALGORITHM TR, ASSIGNINE RELATIVE(* POSITIONINGS TO ALL NODES IN TEE TREE POINTED TO BY PARAMETER T.
VAR

L,ER LENK;
LR, LL, RR, EL : EXTREME;(* LEFT AND RIGHT SONS(* LR - RIGHTMOST NODE ON(* LOWEST LEVEL OF LEFT SUBTREE(* AND SO ON

CURSEP,(* SEPARATION ON CURRENT LEVEL(* CURRENT SEPARATION AT NODE T(R OFPSET FROM L & R TO T

ROOTSEP,LOFPSUM, ROFFSIN: ENTEGER;

*)
*)
*)

BEGIN (* SETUP *)IF T - NIL TREN BEGIN(R AVOED SELECTING AS EXTREME
RI
LMOST.LEV : -l;
RKOST.LEV-S
END ELSE BENIN
T^.YCOORD :- LEVEL;L(R FOLLOWS CONTOUR OF LEFT SUBTREE R)
T^.LLINK;
R - T^.RLINK;(R FOLLOWS CONTOUR OP RIGNT SUBTREE *)SETUP L, LEVEL+SS LR, LL ); (R POSITION SUBTREES RECURSIVELYR)
SETUP RI, LEVEL+1, RR, RL );EF (R-NIL) AND (L-NIL) THEN BEGIN (* LEA)TRMOST.ADDR
C;(* A LEAP IS BOTH THE LEPTMOSTR)(E AND RIGHTMOST NODE ON THE
LMOST.ADDR - T;
R)
RMOST.LEV :- LEVEL;(* LOWEST LEVEL OF THE SUBTREE*)
LMOST.LEV - LEVEL;(S CONSISTING OF ITSELF*)
RMOST.OFF - 0;
LMOST.OFF - 0;
T'.OFPS8T - 0(R T NOT A LEA)END ELSE BEGIN(

SET UP FOR SUBTREE PUSHING.

PLACE ROOTS OF R)(R SUBTREES MINIMUM DISTANCE APART.

R)

CURSEP - MINSEP;ROOTSEP M- INSEP;LOPPSUM
0;
RODFSUM - U;

(R NOW CONSIDER RACH LEVEL IN TURN UNTIL ONE *)(R SUBTREE IS EXHAUSTED, PUSHING THE SUOTREES R)R)(R APART WHEN NECESSARY.

WHILE (L<>NIL) AND (R<>NEL) DO BEGIN
IF CURSEP < MINSEP THEN BEGIN (* PUSH ? *)ROOTSIP - ROOTSEP + (MINSEP - CURSEP);CURSEP - MINSEP
ISD; (* ID CURSEP < MINSEP H)(* ADVANCE L & R *)IF L^.RLINK <> NIL THEN NEGIN
LOFFSPIM - LOPFSUM + L'.OFFSET;CURSEP - CURSEP - L'.OFFSET;
L :- L^.RLiNK

END ELSE BEGIN
LOFFSUMK- LOFFSUM - L^.OFFSET;CURSEP - CURSEP + L^.OFFSET;
L :- L^.LLINKEND;

IF R^.LLINK (> NEL THEN BEGIN
ROFFSUM :- ROFFSUM - R^.OFPSET;CURSEP - CURSEP - R'.OFFSET;
R :- R^.LLINKEND ELSE BEGIN
ROFFSE :- ROFFSUI + R^.OFFSET;CURSEP :- CURSEP + R^.OFFSET;
R :- R.RLINK

END; C* ELSE *)END; (* WHILE *)(* SET THE OFFSET IN NODE T, AND INCLUDE IT IN *)N)(* ACCUMULATED OFFSETS FOR L AND R
T'.OFFSET :- (ROOTSEP + 1) DIV 2;
LOFFSUM : LOFFSUM - T^.OFFSET;ROFFSUM - ROFFSUM + T'.OFFSET;(R UPDATE EXTREME DESCENDANTS INFOREMATIOS R)
IF (RL.LEV > LL.LEV) OR CT^.LLINK - NIL)
LMOST : - RL;
LMOST.OFF :- LMOST.OFF + T^.OFFSET
END ELSE BEGIN
LMOST :- LL;
LMOST.OFF :- LMOST.OFF - T^.OFFSET

THEN BEGIN

END;
IF (LR.LEV > RR.LEV) OR (T^.RLINK - SIL) THEN BEGIN
REOST :- LR;

RMOST.OFF :- RMOST.OFF - T^.OFFSET
END ELSE BEGIN
RMOST :- RR;
RMOST.OFF :- RMOST.OFF + T-.OFFSET

END;(R IF SUBTREES OF T WERE OF UNEVEN HEIGHTS, CKER R)(R TO SEE IF THREADING IS NHECESSARY. AT MOST ONE *)(* THREAD NEEDS TO BE INSERTED.

*)

IF (L 0> NEL) AND (L C> T.LLINK) THEEN BEGIN
RR.ADDRE.THREAD
TRUE;
RR.ADDR'.OFFSET : ABS(( RR.OFF + T^.OFFSET) - LOFFSUM );IF LOFFSUM - T^.OFFSET <- R.OFF THEN

RR.ADDR'.LLINK - L

ELSE

RR.ADDR.RLINK - L

END ELSE IF (R <> NIL) AND (R > T^.RLINK) THEN BEGIN
LL.ADDR'.THREAD - TRUE;
LL.ADDR'.OFFSET A- BS(( LL.OFF - T^.OFFSET ) - ROFFSUM );IF ROFFSUM + T'.OFFSET >- LL.OFF THEN

LL.ADDR'.RLINK

ELSE
END

R

LL.ADDR'.LLINK- R

ESD; (* OF IF NOT LEAF *)END; (* OF T C> NIL *)END; (* PROCEDURE SETUP *)Fig. 6. Procedure SETUP assigns relative x coordinates to all nodes during a postorder traversal.

its sons. We store this relative distance rather than the absolute location so that subtrees can be pushed apart easily.
Storing this offset field in the father rather than sons may
not be a good idea for m-ary trees and forests, but for reasons

226

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-7, NO. 2, MARCH 1981

that will become apparent this method is preferable for binary
trees. A node of the tree, then, has the following format (forthe sake of clarity we have reserved space for both OFFSET
and XCOORD, although clearly these can share the same spacein a real implementation):
NODE = RECORDINFOLLINK,RLINK : LINK;XCOORD,YCOORD: INTEGER;OFFSET : IN-TEGER;THREAD: BOOLEAN
END;(* whatever *)(* pointers to subtrees *)(* coordinates of this node *)(* distance to each son *)(* address *)(* offset from root of subtree *)(* tree level *)If the current subtree is a single node, then that node istrivially both the leftmost and rightmost node on the lowest
level of the subtree; otherwise, its extreme descendants caneasily be chosen from among the extreme descendants of its
sons.

PROCEDURE PETRIFY ( T: LINK; XPOS: COLUMN );(* THIS PROCEDURE PERFORMS A PREORDER TRAVERSAL OF THE TREE,(* CONVERTING THE RELATIVE OFFSETS TO ABSOLUTE COORDINATES.

The first task is determining the separation of the subtrees.
This is accomplished by the while loop in Fig. 6. It scans
down the right contour of the left subtree and the left contourof the right subtree, computing the distance between them,and pushing them apart when necessary. Variables L and R
are initially set to point to the left and right son, respectively,of T. MINSEP is a parameter that gives the minimum separation
allowed between two nodes on a level; CURSEP holds theseparation at the current level. ROOTSEP accumulates therequired separation distance for the sons of T so that theirsubtrees will have a separation of at least MINSEP at all levels.
LOFFSUM and ROFFSUM accumulate the total offset of thecurrent L and R from the root; this information is needed tocompute offsets of threaded nodes.
The second task is to keep track of the leftmost and rightmost nodes on the lowest level of the subtree; only thesenodes could ever be threaded. Information conceming these
extreme descendants is stored in the following record format:
EXTREME = RECORDADDR : LINK;
OFF : INTEGER;
LEV : INTEGER
END;

Fig. 7. The dashed lines represent threads used to follow the contoursof subtrees.

Threading, the third task, is needed only if the subtrees
joined at the current node have different heights and neither
is empty. If the left subtree, say, is taller, a thread must be
inserted from the rightmost node on the lowest level of theright subtree to the rightmost node on the next lower levelof the left subtree (Fig. 7). The former node is an extreme
descendant that has been determined by the second task ina previous activation of SETUP, and the variable L is currently pointing to the latter node, so inserting the thread withthe appropriate offset is a simple matter. The thread is stored
in the left link field if the node to which it points is to its
left, and in the right link field otherwise; this makes thethreads transparent as the subtrees are pushed apart. This
convenience is the motivation for storing offsets in fathers

BEGIN
IF T <> NIL THEN BEGIN
T^.XCOORD :- XPOS;
IF T^.THREAD THEN REGIN
T^.THREAD F- ALSE;T^.RLINK - NIL;T^.LLINK
NIL

(

H)

*)

THREADEED NODE MRST BE A LEAF *)ENDI

PETRIFY ( T^.LLIiK, XPOS - T'.OFFSET );PETRIFY ( T^.RLINK, XPOS + T'.OFFsEr
END (* IF T <> NIL
END; (* PETRIFY *)Fig. 8. Procedure PETRIFY converts relative positionings to absolutecoordinates.

rather than sons. Although a node can be threaded to at
most one other node, a node might be pointed to by two
active threads; thus, if offsets were stored in sons, extra space
would have to be reserved in each node for two thread offsets,complicating both the data structure and the algorithm.
The relative positionings need to be converted to absolutecoordinates after procedure SETUP is finished. A simple
routine can scan the left contour of the tree to find the offset
from the leftmost node to the root. Lastly, procedure PETRIFY(shown-in Fig. 8) -computes the final position of each node,and erases all the threads as well.

MATHEMATICAL ANALYSISThe algorithm does not-appear to be-cost effective because
it must examine the contour of the subtrees of every node in
the tree. However, the requirement that scanning must proceed only to the depth of the shorter subtree of each node
makes the running time linear in the number of nodes in thetree and hence comparable to that of Algorithm WS.
The time required by Algorithm TR is completely determined by the while loop because SETUP iS executed exactly
once per node of the tree. To study the behavior of thewhile loop, we need a few definitions. A binary tree is either
empty or consists of a node called the root and two subtrees
T1 and Tr. The size n(T) of a binary tree T is the number ofnodes it contains; its height h(T) is the number of nodes on
the longest path from- the root to a leaf. Thus the tree ofFig. 4 has height 6 (although by the usual definition it hasheight 5).
Note that the while loop is executed only so long as both L
and R are non-nil, that is, only until we have dropped off thecontour of the shorter subtree. The test of the loop fails once
for each node, i.e., n(T) times. Let F(T) be the number oftimes the test of the loop succeeds, i.e., the number of times
the body of the loop is executed for a tree T.
F(nil) - F(.) = 0,

227

REINGOLD AND TILFORD: TIDIER DRAWINGS OF TREES

because the loop is not executed at all for empty trees orleaves. Also,
F /

/

,,

--A--

I

I

--B- C
1
1\= F(T1) + F(Tr) + min [h(TI), h(Tr)1,

D

E

Fig. 9. A tree and its most natural discrete representation.

since the number of times the loop is executed is equal to thesum of the executions for each subtree, plus one iteration at
B--A--Ceach level in the shorter of its subtrees as they are positioned.
We claim that F(T) = n(T) - h(T). The proof is by induction on N, the number of nodes in T. In light of our definitionof height, the truth of the claim at N = 0 and N = 1 is obvious.
I
F
G
H
Suppose the claim is true for trees of less than N nodes; we
for
which
the
Fig.
10.
A
tree
discretestraightforward
representation
show that it is then true for trees containing N nodes. Let T,
is inadequate.
contain k < N nodes; then by the inductive hypothesis,
F(T) = [k - h(T1)] + [N - k - 1 - h(Tr)IA+ min [h(T,), h(Tr)II
C= N - I - h(T,) - h(Tr) + min [h(T,), h(Tr)]B C=N - (max[h(Ti),h(Tr)] + 1).
But the parenthesized expression is exactly h(T), so that
F(T)= n(T) - h(T) and the claim holds for trees with N
nodes.
In retrospect, it is easy to see why the body of the while
loop is executed n(T) - h(T) times. The code there "glues"
two subtrees together; looking across levels of nodes, if there
are k nodes in a level then there are k - 1 gluings that occur atthat level. Summing over all levels except the root (there is nogluing at the root level) gives [n(T)- 1] - [h(T)- 1] since thetotal number of nodes except the root is n(T) - 1 and thetotal number of levels except the root level is h(T) - 1.
Thus, the body of the loop is executed n(T) - h(T) times
and the loop test is made 2n(T) - h(T) times. The procedureis therefore linear in n(T). The best case is a degenerate tree inwhich no node has two sons; then n(T) = h(T) and the loop
body is never executed. The- worst case is a complete binary
tree for which the loop is executed about n(T) - lg n(T) times.
GENERALIZATION TO m-ARY TREES AND FORESTS
Algorithm TR can easily be extended to handle m-ary trees
without affecting its linear performance. Instead of making
one scan at each node to the depth of the shorter of two subtrees, we make m - 1 scans, one for each adja'cent pair of subtrees. As subtrees are combined into "clumps" (the orderin which this is done is unimportant), we scan to the depthof the shorter clump in each case-thus, it is only the tallest
among the m subtrees whose height is not included in the
count of levels scanned. Let F(T) be the number of times the
body of the generalized while loop is executed for an m-ary
tree T; again F(T)= n(T) - h(T) by a simple extension ofeither of the above proofs. Similarly, the number of times
that the test of the while loop fails is (m - 1) n(T).
For m-ary trees and forests we would probably not want toinsist that the separations of the roots of adjacent subtrees ofa given node be equal, so that if the separations were stored in
the father, m - 1 offset fields would be required per node in

E

D

I
F

G

I
H

I

Fig. 11. A revised discrete drawing for the tree of Fig. 10.

m-ary trees and arbitrarily many offset fields in forests. If
we store the offsets in sons instead, we will need only threeoffset fields per node; the extra two are needed to store thedistance from nodes whose threads point to the current node.
Generalizing Algorithm TR for forests is less straightforward
than for m-ary trees and depends heavily on the representation
used. If a forest is represented as the binary tree that arises
from the "natural correspondence" (see [1]), then the required postorder traversal of the forest amounts to an inorder
traversal of the corresponding binary tree. Maintaining thethreads and following the contours between adjacent pairsof subtrees -is made complicated because there is no directaccess from a father to its rightmost son. Following the rightcontour requires going through all of the sons of a node toreach the next node on the contour. Fortunately, the resulting algorithm remains linear in the number of nodes in theforest. Details of the algorithm and its analysis can be foundin [4].
DISCRETIZATION PROBLEMS
Wetherell and Shannon note that some difficulties arise
when alphanumeric output devices are used to produce thetree drawings. On line printer devices the natural way to draw
the tree of Fig. 9 is as shown. But both Algorithm WS and
Algorithm TR run into a problem for many trees in which one
subtree is wide and the other consists of just a few nodes, as
can be seen in Fig. 10. The simple solution is to draw thetree in the way shown in Fig. 11; if we insist that branches
be in the style of Fig. 9, the drawings must be made con-siderably wider.

228

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-7, NO. 2, MARCH 1981

A second issue in discretization is that coordinates must be
given integer values. The positioning of trees by Algorithm
WS, as implemented in [6], frequently fails to satisfy Aesthetic 3 by a small amount. When the distance between
brothers is an odd number, Algorithm WS truncates thecomputed x coordinate of the father, leaving it uncentered.
By forcing a separation of even length between brothers,
Algorithm TR avoids this pitfall. Algorithm WS could be
similarly modified.

CONCLUSIONS
Algorithm TR produces very pleasing drawings in general.
Unfortunately, the drawings can be wider than the minimum
possible under the four aesthetics; this is unavoidable, however, because Supowit and Reingold [2] have shown that
determining the minimum width under these aesthetics is
NP-hard.
REFERENCES[1] D. E. Knuth, The Art of Computer Programming, Vol. 1: FundamentalAlgorithms, 2nd ed. Reading, MA: Addison-Wesley, 1972.
[2] K. J. Supowit and E. M. Reingold, "The complexity of drawing
trees nicely," to be published.
[3] R. E. Sweet, "Empirical estimates of program entropy," Dep.
Comput. Sci., Stanford Univ., Stanford, CA, Rep. STAN-CS-78698, Nov. 1978; also issued as Rep. CSL-78-3, Xerox PARC, Palo
Alto, CA, Sept. 1978.

[4] J. S. Tilford, "Tree drawing algorithms," M.S. thesis, Dep. Comput.
Sci., Univ. Illinois, Urbana, IL, Rep. UIUC DCS-R-81-1055, 1981.
[5] J. G. Vaucher, "Pretty-Printing of Trees," Software-Practice andExperience, vol. 10, pp. 553-561, 1980.
[6] C. Wetherell and A. Shannon, "Tidy drawimgs of trees," IEEE
Trans. Software Eng., vol. SE-5, pp. 514-520, 1979.

Edward M. Reingold received the B.S. degreefrom the Illinois Institute of Technology,
Chicago, IL, and the M.S. and Ph.D. degrees
from Cornell University, Ithaca, NY.
- He is currently an Associate Professor ofComputer Science at the University of 11linois, Urbana-Champaign. H-is areas of specialization are data structures and the analysis ofalgorithms.

John S. Tilfoid received the B.A. degree from
DePauw University, Greencastle, IN, in 1977.
He is currently a Ph.D. candidate in computerscience at the University of Illinois, UrbanaChampaign. His interests include data structures and relational database design theory.