An efficient algorithm for drawing tree structured diagrams

Various algorithms have been proposed for the problem of drawing rooted ordered trees. In one of them, Unno et al presented an O(n³)-time algorithm that (i) produces an initial drawing of a given tree T, and then (ii) finds a narrower drawing by repeatedly moving subtrees (n is the number of vertices in T). In this paper, the authors show that the same drawing can be obtained more efficiently by maintaining the contours of subtrees. If a natural restriction is imposed on the sizes of nodes, the present method can be executed in O(nα (n,n)) time, where α is a functional inverse of Ackermann’s function. [In Japanese.]