A node-positioning algorithm for general trees - Walker, II, John Q. (Software -- Practice and Experience, 1990)
Drawing a tree consists of two stages: determining the position of each node, and actually rendering the individuals nodes and interconnecting branches. The algorithm described in this paper is concerned with the first stage: given a list of nodes, an indication of the hierarchical relationship among them, and their shape and size, where should each node be positioned for optimal aesthetic effect? This algorithm determines the positions of the nodes for any arbitrary general tree. It is the most desirable positioning with respect to certain widely-accepted heuristics. The positioning, specified in x, y co-ordinates, minimizes the width of the tree. In a general tree, there is no limit on the number of offspring per node; this contrasts with binary and ternary trees, for example, which are trees with a limit of two and three offspring per node. This algorithm operates in time O(N), where N is the number of nodes in the tree. Previously, most tree drawings have been positioned by the sure hand of a human graphic designer. Many computer-generated positionings have been either trivial or contained irregularities. Earlier work by Wetherell and Shannon1 and Tilford,2 upon which this algorithm builds, failed to position the interior nodes of some trees correctly. The algorithm presented here correctly positions a tree's node using only two passes. It also handles several practical considerations: alternative orientations of the tree, variable node sizes and out-of-bounds conditions. Radack, also building on Tilford's work, has solved this same problem with a different algorithm which makes four passes.