Drawing Trees:HV-Layout

HV-Layout

An hv-layout of a binary tree is an upward (but not strictly upward) straight line orthogonal drawing with edges drawn as rightward horizontal or downward vertical segments. The ”hv”

image

stands for horizontal-vertical. For any vertex v in a binary tree T we either have:

1. A child of v is either

• aligned horizontally with v and to the right of v or

• vertically aligned below v.

2. The smallest rectangles that cover the area of the subtrees of the children of v in the layout do not intersect.

Figure 45.12 shows an example of a hv-layout

image

A hv-layout is generated by applying a dived and conquer approach. The divide step constructs the hv-layout of the left and the right subtrees, while the conquer step either performs a horizontal or a vertical combination. Figure 45.13 shows the two types of com- bination.

If the left subtree a node v is placed to the left in a horizontal combination and below in a vertical combination, the layout preserves the ordering of the children of v. The height and width of such a drawing is at most |V |1. A straightforward way to reduce the size of a hv-drawing to a height of at most log |V | is to use only horizontal combinations and to place the larger subtree (in terms of number of nodes) to the right of the smaller subtree. This right heavy hv layout is not order preserving and can be produced in O(|V |) requiring

image

As already presented in the introduction, this type of layout has been extensively studied e.g. in [4–7, 10, 12–15, 20–22] to obtain results on minimal area requirements of tree layouts.

Recently Garg and Ruse [11] showed by flipping the subtrees rooted at a node v horizon- tally or vertically, it is possible to obtain tree layouts for binary trees with an O(|V |) area and with a pre specified aspect ratio in the range of [1, |V |α], with α [0, 1). These layouts are non upward straight line orthogonal layouts.

Acknowledgment

I gratefully acknowledge the contributions of Christoph Buchheim, who provided some of the figures and the implementation from our paper [2] and Merijam Percan for her careful proofreading.