Walker's Algorithm for Tree Drawing

Draw Aesthetically Pleasant Trees

Aesthetic Properties

Nodes at the same level should be drawn on the same horizontal line.
The order of the children is reflected in the drawing.
Drawings are symmetric, i.e., the drawing of a reflection of the tree is the reflected drawing of the tree.
A parent node should be centered over their children's nodes.
Subtrees look the same, independent of their position. That is, subtrees should be drawn the same no matter where they are within the tree, i.e., move subtrees rigidly.

Walker's Algorithm

Background

The root is at the top of the drawing.
Tree drawing consists of computing the x- and y-coordinates of the nodes.
The y-coordinate is determined by the level of the node.
Subtrees are handled as rigid units, i.e., moving the root of the subtree moves all its descendants.
The x-coordinates of the nodes are computed recursively from the leaves of the tree.
Two variables are maintained for each node: a preliminary x-coordinate and a modifier field to move the node descendants.

Properties

two-pass algorithm:
- post-order-traversal to compute preliminary x-coordinate and modifier fields
- pre-order-traversal to compute the final node's x-coordinate
a minimal sibling separation distance separates sibling nodes
subtrees are separated by at least a minimal predefined subtree separation
to move a subtree, modifier fields are computed
a subtree is moved by an amount given by the sum of the modifier fields of all its ascendant up to the root node
to keep the tree drawing as narrow as possible, place right subtrees as close as possible to the left sibling subtrees
for this purpose, maintain the left contour of the right subtree and the right contour of the left subtree
compare left and right contours and push the right subtree to avoid overlaps

Algorithm's Complexity

Walker's algorithms for arbitrary n-ary tree has complexity \(\mathcal{O}(n^2)\), where \(n\) is the number of nodes in the tree.

Implementation

Switching between a vertical and circular layout is possible in the drawing below. Moving the mouse over the nodes will reveal the names of the nodes. The mouse wheel can be used to zoom in or out. The left click allows for moving the drawing.