__Level Layout for n-ary Trees__

__Level Layout for n-ary Trees__

A straightforward manner to draw trees of unbounded degree is to adjust the Rein gold Tilford algorithm by traversing the children of each node *v *from left to right, successively computing the preliminary coordinates and the modiﬁers.

This however violates property (A5): the subtrees are placed as close to each other as possible and small subtrees between larger ones are piled to the left; see Figure 45.3(a). A simple trick to avoid this eﬀect is to add an analogous second traversal from right to left; see Figure 45.3(b), and to take average positions after that. This algorithm satisﬁes (A1) to (A5), but smaller subtrees are usually clustered then; see Figure 45.3(c).

To obtain a layout where smaller subtrees are spaced out evenly between larger subtrees as for example shown in Figure 45.3(d), we process the subtrees for each node *v **∈ **V *from left to right, see Figure 45.4. In a ﬁrst step, every subtree is then placed as close as possible to the right of its left subtrees. This is done similarly to the algorithm for binary trees as described in Section 45.3 by traversing the left contour of the right subtree *T *(*w**ri**g**h**t *) and the right contour of the subforest induced by the left siblings of *w**ri**g**h**t *.

Whenever two conﬂicting neighbors *v**left *and *v**ri**g**h**t *are detected, forcing *v**ri**ght *to be shifted to the right by an amount of *σ*, we apply an appropriate shift to all smaller subtrees between the subtrees containing *v**left *and *v**ri**g**h**t *.

More precisely, let *w**left *and *w**ri**g**h**t *be the greatest distinct ancestors of *v**left *and *v**ri**g**h**t *. Notice that both *w**left *and *w**ri**g**h**t *are children of the node *v *that is currently processed. Let *k *be the number of children *w*1*, w*2*,…**, w**k *of the current root between *w**left *and *w**ri**g**h**t *+ 1. The subtrees between *w**left *and *w**ri**g**h**t *are spaced out by shifting the subtree *T *(*w**i*) to the

Based on the results of the function PrePosition the function Adjust given in Algo- rithm 2 computes the ﬁnal coordinates by summing up the modiﬁers recursively.

**PrePosition**

Algorithm 3 presents the method PrePosition(*v*) that computes a preliminary x-coordinate for a node *v*. PrePosition is applied recursively to the children of *v*. After each call

of PrePosition on a child *w *a function Apportion is executed on *w*. The procedure Apportion is the core of the algorithm and shifts a subtree such that it does not conﬂict with its left subforest. After spacing out the smaller subtrees by calling Execute Shifts, the node *v *is placed to the midpoint of its outermost children. The value *di**stance *pre- scribes the minimal distance between two nodes. If objects of diﬀerent size are considered for the representation of the nodes, or if diﬀerent minimal distances, i.e. between subtrees, are speciﬁed, the value *di**stance *has to be modiﬁed appropriately.

Combining a Subtree and Its Left Subforest

Before presenting Apportion in detail, we need to consider eﬃcient strategies for the diﬀerent tasks that are performed by this function.

Similar to the threads used for binary trees (see Sect. 45.3), Apportion uses threads to follow the contours of the right subtree and the left subforest. The fact that the left subforest is no tree in general does not create any additional diﬃculty.

One major task of Apportion is that it has to space out the smaller subtrees between the larger ones. More precisely, if Apportion shifts a subtree to the right to avoid a conﬂict with its left subforest, Apportion has to make sure that the shifts of the smaller subtrees of the left subforest are determined.

A straightforward implementation computes the shifts for the intermediate smaller sub- trees after the right subtree has been moved. However, as has been shown in [2], this strategy has an aggregated runtime of Ω(*|**V *3*/*2 ). To prove this consider a tree *T **k *such that the root has *k *children *v*1*, v*2*,..**. , v**k *(see Figure 45.7 for *k *= 3). The children are numbered from left to right. Except for *v*1 let the *i*-th child *v**i *be the root of a subtree *T **k*(*v**i*) that consist of a chain of *i *nodes. Between each pair *v**i*, *v**i*+1, *i *= 1*, *2*,..**. ,k **− *1, of these children, add *k *children as leaves. Moreover, the subtree *T **k*(*v*1) is modiﬁed as follows. Its root *v*1 has 2*k *+ 5 children, and up to level *k **− *1, every rightmost child of the 2*k *+ 5 children again

The next Section 45.4.3 shows how to obtain the tree *T *(*v**j *) eﬃciently. Section 45.4.4 gives a detailed description on how to compute the shift of *T *(*v**i*) and Section 45.4.5 presents a method that spaces out smaller subtrees.

**Ancestor**

We ﬁrst describe how to obtain the subtree *T *(*v**j *) that contains the node *v**left *. The problem is equivalent to ﬁnding the greatest distinct ancestors *w**left *and *w**ri**g**h**t *of the nodes *v**left** *and *v**ri**g**h**t *, where in this case *w**left *is equal to the root *v**j *of the subtree that we need to determine and *w**ri**g**h**t *= *v**i*. It is possible to apply an algorithm by Schieber and Vishkin [19] that determines for each pair of nodes its greatest distinct ancestors in constant time, after an *O*(*|**V **|*) preprocessing step. Since their algorithm is somewhat tricky, and one of the greatest distinct ancestors, namely *v**i*, is known anyway, we apply a much simpler algorithm. Furthermore, as *v**ri**g**h**t *is always the right neighbor of *v**left *, the left one of the greatest distinct ancestors only depends on *v**left *. Thus we may shortly call it *the ancestor *of *v**left *in the following.

FIGURE 45.8: Adjusting ancestor pointers when adding new subtrees: the pointer *a**ncestor *(*u*) is represented by a solid arrow if it is up to date and by a dashed arrow if it has expired. In the latter case, the *d**e**fa**u**ltAncestor *is used and drawn black. When adding a small subtree, all ancestor pointers *a**ncestor *(*u*) of its right contour are updated. When adding a large subtree, only *d**e**fa**u**ltAncestor *is updated.

To store the ancestor of a node *u *a pointer *a**ncestor *(*u*) is introduced and initialized to *u *itself. The pointer *a**ncestor *(*u*) for any node *u *is not updated throughout the algorithm. Instead, a *d**e**fa**u**ltAncestor *is used and ancestors are only determined for the nodes *u *on the

Shifting the Smaller Subtrees

For spacing out the smaller subtrees evenly, the number of the smaller subtrees between the larger ones has to be maintained. Since simply counting the number of smaller children between two larger subtrees *T *(*v**j *) and *T *(*v**i*), 1 *≤ **j** **< i **≤ **k *would result in Ω(*n*3*/*2) time in total, it is determined as follows. The children of *v *are numbered consecutively. Once the pair of nodes *v**left **, v**ri**g**h**t *that deﬁnes the maximum shift on *T *(*v**i*) has been determined, the greatest distinct ancestors *w**left *= *v**j *and *w**ri**g**h**t *= *v**i *are easily determined by the approach described in Section 45.4.3. The number *i **− **j **− *1 gives the number of in between subtrees in constant time.

1. the value

shift(vi) is increased byσ2. the value

change(vi) is decreased byσ/θ3. the value

change(vj) is increased byσ/θ

Figure 45.9 shows an example on setting the values of *shift *() and *c**ha**nge*(). By construction of the arrays *shift *() and *c**ha**nge*() we then obtain the shift of *T *(*v**g *), *g *= 1*, *2*,..**. , k*, (including the “original” shift of the subtree *T *(*v**i*)) as follows. The children *v**g *, *g *= *k**, k **− *1*,..**. , *1, are traversed from right to left. Two real values *σ *and *c**ha**nge *are maintained to store the shifts and the decreases of shift per subtree, respectively. These values are initialized with zero. When visiting child *v**g *, *g **∈ {**k**, k**−*1*,..**. , *1*} *the subtree *T *(*v**g *) is shifted to the right by *σ *(i.e., we increase *p**r**eli**m*(*v**g *) and *mod *(*v**g *) by *σ*). Furthermore, *c**ha**nge *is increased by *c**ha**nge*(*v**g *), and *σ *is increased by *shift *(*v**g *) and by *c**ha**nge*(*v**g *) and we continue with *v**g**−*1.

The function ExecuteShifts(*v*) traverses its children from right to left and determines the total shift of the children based on the arrays *shift *() and *c**ha**nge*().

*T**HEOREM 45.2 **[B**u**chheim et al. [2]] The layout algorithm for **n**-ary trees meets the aes-** **thetic requirements (A1)–(A5), spaces out smaller subtrees evenly, and can be implemented **to run in **O*(*|**V **|*)*.*

**Proof **By construction of the algorithm it is obvious that the algorithm meets (A1)–(A5) and spaces out the smaller subtrees evenly. So it is left to show that the running time is linear in the number of nodes.

Every node of *T *is traversed once during the traversals PrePosition and Adjust.

Similar reasoning as in the proof of theorem 45.1 for binary trees shows that the time needed to traverse the left contour of the subtree *T *(*v**i*) and the right contour of subforest *∪**h*=1*T *(*v**h*), *i *= 2*, *3*,..**. ,k *for every node *v *with children *v**i*, *i *= 1*, *2*,..**. ,k *is linear in the number of nodes of *T *over all such traversals. Moreover, we have that by construction the number of extra operations for spacing out the smaller subtrees is linear in *|**V **| *plus the number of nodes traversed in the contours. This proves the theorem.