A linear algorithm for compact box‐drawings of trees
M.A. Hasan, Md. Saidur Rahman, Takao Nishizeki · Networks · 2003
Abstract 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(n2) if a tree has n nodes. © 2003 Wiley Periodicals, Inc.