Browse Prior Art Database

# Improved Graph Layout Algorithm for Trees with Fan-In

IP.com Disclosure Number: IPCOM000116983D
Original Publication Date: 1995-Dec-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 130K

IBM

## Related People

Llames, RL: AUTHOR

## Abstract

Disclosed is an algorithm for graph layout which represents an improvement to the Robins algorithm (1). One improvement is to detect and eliminate node overlap. The second improvement is a heuristic in which coordinates are assigned to the nodes in a particular (rather than arbitrary) order, such that a clustering effect is achieved for trees with pervasive fan-in.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 44% of the total text.

Improved Graph Layout Algorithm for Trees with Fan-In

Disclosed is an algorithm for graph layout which represents an
improvement to the Robins algorithm (1).  One improvement is to
detect and eliminate node overlap.  The second improvement is a
heuristic in which coordinates are assigned to the nodes in a
particular (rather than arbitrary) order, such that a clustering
effect is achieved for trees with pervasive fan-in.

To explain these improvements in more detail, the Robins algorithm is
described first.

The Robins algorithm is a relatively simple algorithm for
performing tree-oriented graph layout.  This algorithm is fast (O(n)
in the number of graph nodes), simpler and easier to implement than
earlier algorithms, and results in a reasonably attractive layout.
Speed and simplicity is achieved because the algorithm is based on
heuristics rather than rigorous mathematical optimization of some
measure of goodness, such as symmetry or number of edge crossings.

The algorithm assigns x coordinates to the nodes independently
of y coordinates as follows.  Assume that the tree is drawn with
roots at the top, and that x and y coordinates are increasing
leftward and upward, respectively.  (The generalization to other tree
orientations and coordinate systems is straightforward.)

A node's y coordinate is set to the minimum of the y
coordinates of its parents minus some fixed depth separation.  This
rule can be implemented by first topologically sorting the nodes and
then assigning y coordinates to the nodes in the order that they
appear in the sorted list.  (A topological sort produces a
not-necessarily-unique ordered list of the nodes in which a node
appears after all its parent nodes and before all its child nodes.)

A node's x coordinate depends on whether or not it is a leaf
node.  If a node is a leaf, its x coordinate is set to the x
coordinate last assigned to a leaf plus some fixed breadth
separation.  If a node is not a leaf, its x coordinate is set to the
average of its child nodes' x coordinates.  This rule can be
implemented by assigning x coordinates to nodes either during a
post-order depth-first traversal of the tree, or during a reverse
scan of the topologically sorted list of nodes.

However, Robins algorithm fails for graphs other than strict
trees, in particular, for a tree in which a node may have more than
one parent node.  The layout algorithm fails in the sense that it may
result in overlapping nodes.

An example of such a graph is a class inheritance graph
involving multiple inheritance.  The problem is especially severe for
trees with pervasive fan-in, that is, where there are a few nodes
with many parents, or many nodes each having a few parents.

The improvements to the algorithm, which are the subject of
this disclosure, involve the assignment of x coordinates and are
described as follows.  The assignment of y coordinates is unchan...