Next: Horizon Tree
Up: Visualization of Navigation
Previous: Layout strategies
The layout algorithm used in the current implementation of WebMap
to calculate the node positions for a spanning tree is based on
the following principles:
Assume a new node is to be inserted into an existing tree as child
of the node 
.
The precondition is characterized by:
- All leaf nodes have even x-coordinates.
- The horizontal distance between two neighboring leaves is 2.
- The y-coordinate of the root node is zero.
The y-coordinate of is the y-coordinate of incremented by one.
If is the first child of the x-coordinate will be the same
as 's. Otherwise assume 
is the sibling to the left of .
's x-coordinate will be the one of 's rightmost descendant
incremented by 2.
After determining the position of the new node all nodes
of the tree ``above'' and ``to the right'' of are moved to
a new position using a simple recursion:
- The x-coordinates of all right siblings of and the nodes
of their subtrees are incremented by two.
- The x-coordinate of parent node is incremented by one.
- If is not the root node, set to and to
its parent node and repeat this procedure.
This is illustrated in Fig. 5. The nodes which moved to the
right after the insertion of a new node with the x-coordinate 8 are
surrounded by a dotted line.
The algorithm causes each node to be located one level above its children
and in the middle between its leftmost and its rightmost descendant,
which means that its x-coordinate 
always satisfies the following
equation:
Here 
is the x-coordinate of 's leftmost descendant and
is the breadth of 's subtree.
Note, that all node's coordinates are represented by integer values.
Next: Horizon Tree
Up: Visualization of Navigation
Previous: Layout strategies