A linear algorithm for compact box-drawings of trees
In a box-drawing of a rooted tree, each node is drawn by a rectangular box of prescribed size, no two boxes overlap each other, all boxes corresponding to siblings of the tree have the same x-coordinate at their left sides, and a parent node is drawn at a given distance apart from its first child. A box drawing of a tree is compact if it attains the minimum possible rectangular area enclosing the drawing. We give a linear-time algorithm for finding a compact box-drawing of a tree. A known algorithm does not always find a compact box-drawing and takes time O(n(2)) if a tree has n nodes. (C) 2003 Wiley Periodicals, Inc.
algorithm box-drawing graph drawing tree drawing compact drawing