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

Abstract

We investigate the problem of drawing an arbitrary n-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(nlogn) area, which we show is optimal to within constant factors in the worst case (i.e. there are trees that need $\text{Ω(n}\text{log}\text{n)}$ area for any upward orthogonal straight-line drawing with good aspect ratio). An improvement for non-upward drawings is briefly mentioned.