Optimizing area and aspect ratio in straight-line orthogonal tree drawings

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.