*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”

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

vand to the right ofvor• 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

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 *ho**rizontal *or a *ver**t**i**c**a**l 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 *ri**gh**t heavy **hv **layo**u**t *is not order preserving and can be produced in *O*(*|**V **|*) requiring

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 ﬂipping 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 speciﬁed 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 ﬁgures and the implementation from our paper [2] and Merijam Percan for her careful proofreading.