TY - GEN
T1 - Optimizing area and aspect ratio in straight-line orthogonal tree drawings
AU - Chan, Timothy
AU - Goodrich, Michael T.
AU - Kosaraju, S. Rao
AU - Tamassia, Roberto
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: tmchan@uwaterloo.ca (T.M. Chan), goodrich@cs.jhu.edu (M.T. Goodrich), kosaraju@cs.jhu.edu (S.R. Kosaraju), rt@cs.brown.edu (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.
Publisher Copyright:
© 1997, Springer-Verlag. All rights reserved.
PY - 1997
Y1 - 1997
N2 - We investigate the problem of drawing an arbitrary n-node binary tree orthogonally 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 being O(1) or sometimes even an arbitrary parameter. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call “subtree separation,” We investigate both upward and non-upward drawings, achieving area bounds of O(n log n) and O(n log log n), respectively, and we show that, at least in the case of upward drawings, our area bound is optimal to within constant factors.
AB - We investigate the problem of drawing an arbitrary n-node binary tree orthogonally 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 being O(1) or sometimes even an arbitrary parameter. In addition, we show that one can also achieve an additional desirable aesthetic criterion, which we call “subtree separation,” We investigate both upward and non-upward drawings, achieving area bounds of O(n log n) and O(n log log n), respectively, and we show that, at least in the case of upward drawings, our area bound is optimal to within constant factors.
UR - http://www.scopus.com/inward/record.url?scp=84957683304&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84957683304&partnerID=8YFLogxK
U2 - 10.1007/3-540-62495-3_38
DO - 10.1007/3-540-62495-3_38
M3 - Conference contribution
AN - SCOPUS:84957683304
SN - 3540624953
SN - 9783540624950
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 63
EP - 75
BT - Graph Drawing - Symposium on Graph Drawing, GD 1996, Proceedings
A2 - North, Stephen
PB - Springer
T2 - Symposium on Graph Drawing, GD 1996
Y2 - 18 September 1996 through 20 September 1996
ER -