A near-linear area bound for drawing binary trees
Timothy M. Chan · 1999
We present several simple methods to construct planar, strictly upward, strongly order-preserving, straight-line drawings of any n-node binary tree. In particular, it is shown that O(n 1+" ) area is always sufficient for an arbitrary constant " ? 0. 1 Introduction What is a good way to draw a given binary tree? Several natural criteria come to mind. As are usually depicted in computer science textbooks, drawings should be: 1. Planar. Nodes are drawn as distinct points in the plane, and if node u is a child of node v, a polygonal curve ("polyline") should be drawn connecting u and v. We want to ensure that no two curves cross. 2. Strictly upward. To see which is the parent/child in a curve, we may require that the curve from the parent to the child is strictly decreasing in the y- direction. 3. Strongly order-preserving. To tell which is the left/right child of a given node, we may require that the curve from the parent to the left child is monotone decreasing in the x-direction,...