Changqing Hu : cs252 Final Project (1998)

Layered Drawing of Rooted Trees

What Is A Layered Drawing for Rooted Trees?

A Layered Drawing of a tree T is a drawing of T such that a vertex v of depth i has y-coordinate y(v) = -i. An algorithm constructs a drawing by computing the x-coordinates. We implement two methods for assigning x-coordinates. One is to set x(v) equal the rank of v in the inorder traversal of T, it works only for binary trees. Another one is by Reingold and Tilford (1983), it is a recursive drawing algorithm. For binary trees, after drawing the left and right subtrees, place the drawings of the subtrees at horizontal distance 2; place the root one level above and half-way between the children; however, if there is only one child, place the root at horizontal distance 1 from the child. This algorithm (Reingold and Tilford) has a straightforward generalization to rooted trees.

How To Use This Applet?

You can first set what kind trees (binary or rooted) you want to draw (the default is binary tree), and which drawing algorithm (Reingold-Tilford or inorder) you want to use (the default is Reigold-Tilford, and for rooted trees, you can use this algorithm only, the choice for inorder will be changed to R-T automatically), by clicking on named buttons below the first canvas. Then you can input your tree in the first canvas. You can either click on any point as the root or draw a line which will contains the root and its first child, then you can expand your tree by adding lines to any node. Note that if you choose a binary tree mode, any line to a node already with two children will be ignored. You are not allowed to draw the tree upward (the segment will be ignored). You may delete a node and all its children, to do this, you click on the delete button first to activate it (the button is checked), then click on the node you intend to delete. To deactivate delete function, click on the delete button again to make sure the button unchecked. After you draw a legal line (mouse-up), the layered drawing for you current tree will be displayed in the second canvas. You can move the displayed tree by clicking and dragging it.

Where To Find More Information on the Algorithm?

You can read the book "Graph Drawing" by G. Battista, P. Eades, R. Tamassia, and I.G. Tollis. Draft available here.