TY - JOUR
T1 - Optimizing area and aspect ratio in straight-line orthogonal tree drawings
AU - Chan, Timothy M.
AU - Goodrich, Michael T.
AU - Rao Kosaraju, S.
AU - Tamassia, Roberta
N1 - Funding Information:
✩ This work is a consequence of the participation of Drs. Goodrich and Tamassia in the 1996 International Workshop on 3D Graph Drawing at Bellairs Research Inst. of McGill University. * Corresponding author. E-mail addresses: [email protected] (T.M. Chan), [email protected] (M.T. Goodrich), [email protected] (S.R. Kosaraju), [email protected] (R. Tamassia). 1This research was performed while the author was visiting the Center for Geometric Computing at Johns Hopkins University, and it was supported in part by ARO under grant DAAH04-96-1-0013. 2 This research supported by NSF under Grant CCR-9300079 and by ARO under grant DAAH04-96-1-0013. 3 This research supported by NSF under Grant CCR-9508545 and by ARO under grant DAAH04-96-1-0013. 4 This research supported by NSF under Grant CCR-9423847 and by ARO under grant DAAH04-96-1-0013.
PY - 2002
Y1 - 2002
N2 - We investigate the problem of drawing an arbitrary «-node binary tree orthogonally and upwardly in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as a fixed constant or a parameter under the user's control. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call "subtree separation". Our drawings require O(;i log«) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need £2 (H log«) area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.
AB - We investigate the problem of drawing an arbitrary «-node binary tree orthogonally and upwardly in an integer grid using straight-line edges. We show that one can simultaneously achieve good area bounds while also allowing the aspect ratio to be chosen as a fixed constant or a parameter under the user's control. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call "subtree separation". Our drawings require O(;i log«) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need £2 (H log«) area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.
KW - Binary trees
KW - Graph drawing
UR - http://www.scopus.com/inward/record.url?scp=31244433077&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=31244433077&partnerID=8YFLogxK
U2 - 10.1016/S0925-7721(01)00066-9
DO - 10.1016/S0925-7721(01)00066-9
M3 - Article
AN - SCOPUS:31244433077
SN - 0925-7721
VL - 23
SP - 153
EP - 162
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 2
ER -