Drawing Trees:Introduction and Preliminaries

Introduction

Constructing geometric representations of graphs in a readable and efficient way is crucial for understanding the inherent properties of the structures in many applications. The desire to generate a layout of such representations by algorithms and not by hand meeting certain aesthetics has motivated the research area Graph Drawing. Examples of these aesthetics include minimizing the number of edge crossings, minimizing the number of edge bends, minimizing the display area of the graph, visualizing a common direction (flow) in the graph, maximizing the angular resolution at the vertices, and maximizing the display of symmetries. Certainly, two aesthetic criteria cannot be simultaneously optimized in general and it depends on the data which criterion should be preferably optimized. Graph Drawing Software relies on a variety of mathematical results in graph theory, topology, geometry, as well as computer science techniques mainly in the areas algorithms and data structures, software engineering and user interfaces.

A typical graph drawing problem is to create for a graph G = (V, E) a geometric representation where the nodes in V are drawn as geometric objects such as points or two dimensional shapes and edges (u, v) ∈ E are drawn as simple Jordan curves connecting the geometric objects associated with u and v. Apart from the, in the context of this book obvious, visualization of Data Structures, other application areas are, e.g., software engineering (Unified Modeling Language (UML), data flow diagrams, subroutine-call graphs) databases (entity-relationship diagrams), decision support systems for project management (business process management, work flow).

A fundamental issue in Automatic Graph Drawing is to display trees, since trees are a common type of data structure (Chapter 3).

Thus a good drawing of a tree is often a powerful intuitive guide for analyzing data structures and debugging their implementations. It is a trivial observation that a tree T = (V, E) always admits a planar drawing, that is a drawing in the plane such that no two edges cross. Thus all algorithms that have been developed construct a planar drawing of a tree. Furthermore it is noticed that for trees the condition |E| = |V |− 1 holds and therefore the time complexity of the layout algorithms is always given in dependency to the number of nodes |V | of a tree.

In 1979, Wetherell and Shannon [24] presented a linear time algorithm for drawing binary trees satisfying the following aesthetic requirements: the drawing is strictly upward, i.e. the y-coordinate of a node corresponds to its level, so that the hierarchical structure of the tree is displayed; the left child of a node is placed to the left of the right child, i.e., the order of the children is displayed; finally, each parent node is centered over its children. Moreover, edges are drawn straight line. Nevertheless, this algorithm showed some deficiencies. In 1981, Reingold and Tilford [17] improved the Wetherell-Shannon algorithm by adding the following feature: each pair of isomorphic subtrees is drawn identically up to translation, i.e., the drawing does not depend on the position of a subtree within the complete tree. They also made the algorithm symmetrical: if all orders of children in a tree are reversed, the computed drawing is the reflected original one. The width of the drawing is not always minimized subject to these conditions, but it is close to the minimum in general. The algorithm of Reingold and Tilford that runs in linear time, is given in Section 45.3. Figure 45.1 gives an example of a typical layout produced by Reingold and Tilford’s algorithm.

Extending this algorithm to rooted ordered trees of unbounded degree in a straightforward way produces layouts where some subtrees of the tree may get clustered on a small space, even if they could be dispersed much better. This problem was solved in 1990 by the quadratic time algorithm of Walker [23], which spaces out subtrees whenever possible. Very recently Buchheim et al. [2] showed how to improve the algorithm of Walker to linear running time. The algorithm by Buchheim et al. is given in Section 45.4, including a pseudo code that allows the reader a straightforward application of the algorithm. This algorithm for n-ary trees gives similar results on binary trees as the algorithm of Reingold and Tilford.

In Section 45.5 algorithms for straight line circular drawings (see [1, 8, 9, 16]) are intro- duced. This type of layout proved to be useful for free trees that do not have a designated node as a root. Section 45.6 presents hv-drawings, an approach for drawing binary and n-ary trees on a grid. For binary trees, edges in an hv-drawing are drawn as rightward horizontal or downward vertical segments. This type of drawing is straight line upward orthogonal. It is, however, not strictly upward. Such drawings are e.g. investigated in [4, 5, 12–15, 20, 22].

Variations of the hv-layout algorithms have been used to obtain results on minimal area requirements of tree layouts. Shiloach and Crescenzi et al. [4, 20] showed that any rooted

tree admits an upward straight-line drawing with area O(|V | log |V |). Crescenzi et al. [4]

moreover proved that there exists a class of rooted trees that require Ω(|V | log |V |) area if drawn strictly upward straight-line. In [4, 7] algorithms are given that produce O(|V |)-area

strictly upward straight line drawings for some classes of balanced trees such as complete binary trees, Fibonacci trees, and AVL trees. These results have been expanded in [6] to a class of balanced trees that include k-balanced trees, red-black trees, BB[α]-trees, and (a, b)-trees.  Garg et al. [10] gave an O(|V | log |V |) area algorithm for ordered trees that produces upward layouts with polyline edges. Moreover they presented an upward orthogonal (not necessarily straight line) algorithm with an asymptotically optimal area of O(|V | log log |V |).

Shin et al. [21] showed that bounded degree trees admit upward straight line layouts with an O(|V | log log |V |) area. The result can be modified to derive an algorithm that gives an upward polyline grid drawing with an O(|V | log log |V |) area, at most one bend per edge, and O(|V |/ log |V |) bends in total. Moreover in [21] an O(|V | log log |V |) area algorithm has been presented for non upward straight line grid layouts with arbitrary aspect ratio. Recently, Garg and Rusu [11] improved this result giving for binary trees an O(|V |) area algorithm for non upward straight line orthogonal layouts with a pre specified aspect ratio in the range of [1, |V |α], with α ∈ [0, 1) that can be constructed in O(|V |).

Preliminaries

A (rooted) tree T is a directed acyclic graph with a single source, called the root of the tree, such that there is a unique directed path from the root to any other node. The level l(v) of a node v is the length of this path. The largest level of any node in T is the height h(T ) of T . For each edge (v, w), v is the parent of w and w is a child of v. Children of the same node are called siblings. Each node w on the path from the root to a node v is called an ancestor of v, while v is called a descendant of w. A node that has no children is a leaf. If v1 and v2 are two nodes such that v1 is not an ancestor of v2 and vice versa, the greatest distinct ancestors of v1 and v2 are defined as the unique ancestors w1 and w2 of v1 and v2, respectively, such that w1 and w2 are siblings. Each node v of a rooted tree T induces a unique subtree T (v) of T with root v.

Binary trees are trees with a maximum number of two children per node. In contrast to binary trees, trees that have an arbitrary number of children are called n-ary trees. A

tree is said to be ordered if for every node the order of its children is fixed. The first (last) child according to this order is called the leftmost (rightmost) child. The left (right) sibling of a node v is its predecessor (successor) in the list of children of the parent of v. The leftmost (rightmost) descendant of v on a level l is the leftmost (rightmost) node on the level l belonging to the subtree T (v) induced by v. Finally, if w1 is the left sibling of w2, v1 is the rightmost descendant of w1 on some level l, and v2 is the leftmost descendant of w2 on the same level l, the node v1 is called the left neighbor of v2 and v2 is the right neighbor of v1.

To draw a tree into the plane means to assign x- and y-coordinates to its nodes and to represent each edge (v, w) by a straight line connecting the points corresponding to v and w. Objects that represent the nodes are centered above the point corresponding

to the node. The computation of the coordinates must respect the sizes of the objects. For simplicity however, we assume throughout this paper that all nodes have the same dimensions and that the minimal distance required between neighbors is the same for each pair of neighbors. Both restrictions can be relaxed easily, since we will always compare a single pair of neighbors.

Reingold and Tilford have defined the following aesthetic properties for drawings of trees:

(A1) The layout displays the hierarchical structure of the tree, i.e., the y-coordinate of a node is given by its level.

(A2) A parent is centered above its children.

(A3) The drawing of a subtree does not depend on its position in the tree, i.e., isomorphic subtrees are drawn identically up to translation.

By their appearance, these drawings are called level drawings. If the tree that has to be drawn is ordered, we additionally require the following:

(A4) The order of the children of a node is displayed in the drawing, thus a left child is placed to the left with a smaller x-coordinate and a right child is placed to the right with a bigger x-coordinate.

(A5) A tree and its mirror image are drawn identically up to reflection.

Here, the reflection of an ordered tree is the tree with reversed order of children for each parent node. It is desirable to find a layout satisfying (A1) to (A5) with a small width. However, it has been shown by Supovit and Reingold [18] that achieving the minimum grid width is NP-hard. Moreover, there is no polynomial time algorithm for achieving a width that is smaller than 25 time the minimum width, unless P = NP. If on the other hand continuous coordinates instead of integral coordinates are allowed, minimum width drawing can be found in linear time by applying linear programming techniques (see [18]).