Tidier Drawings of Trees (PDF; 6 pages)

By Edward M. Reingold and John S. Tilford

IEEE Trans. Software Engineering 7 (1981), 223-228

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 some difficulties that lead to aesthetically unpleasing, wider than necessary drawings. We then present a new algorithm with comparable time and storage 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.

The Complexity of Drawing Trees Nicely (PDF; 16 pages)

By Kenneth J. Supowit and Edward M. Reingold

Acta Informatica 18 (1983), 377-392

We investigate the complexity of producing aesthetically pleasing drawings of binary trees, drawings that are as narrow as possible. The notion of what is aesthetically pleasing is embodied in several constraints on the placement of nodes, relative to other nodes. Among the results we give are: (1) There is no obvious "principle of optimality" that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees. (2) A previously suggested heuristic can produce drawings on n-node trees that are O(n) times as wide as necessary. (3) The problem can be reduced in polynomial time to linear programming; hence, if the coordinates assigned to the nodes are continuous variables, then the problem can be solved in polynomial time. (4) If the placement is restricted to the integral lattice then the problem is NP-hard, as is its approximation to within a factor of about 4 per cent.

On the complexity of drawing trees nicely: corrigendum (PDF; 5 pages) By Thorsten Akkerman, Christoph Buchheim, Michael Jünger, and Daniel Teske Acta Informatica 40 (2004), 603-607

Graph Drawing by Force-Directed Placement (PDF; 36 pages)

By Thomas M. J. Fruchterman and Edward M. Reingold

Software-Practice and Experience 21 (1991), 1129-1164

We present a modification of the spring-embedder model of Eades for drawing general undirected graphs with straight edges. Our heuristic strives for uniform edge lengths, and we develop it in analogy to forces in natural systems, for a simple, elegant, conceptually-intuitive, and efficient algorithm.

Back to Edward Reingold's Homepage