Premium
A linear algorithm for compact box‐drawings of trees
Author(s) -
Hasan Masud,
Rahman Md. Saidur,
Nishizeki Takao
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10092
Subject(s) - tree (set theory) , node (physics) , mathematics , algorithm , combinatorics , computer science , structural engineering , engineering
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. © 2003 Wiley Periodicals, Inc.