A linear algorithm for compact box-drawings of trees - Masud Hasan; Md. Saidur Rahman; Takao Nishizeki (CCCG'02: Proceedings of the Canadian Conference on Computational Geometry, 2002)
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.