Drawing Trees

  

 

Input description: A tree T, which is a graph without any cycles.

Problem description: A nice drawing of the tree T.

Discussion: There are as many reasons to want to draw trees as there are types of structures that trees represent. Consider software and debugging tools that illustrate the hierarchical structure of file system directories, or that trace the execution of a program through its subroutines.    

The primary issue in drawing trees is establishing whether you are drawing free or rooted trees:

• Rooted trees define a hierarchical order, emanating from a single source node identified as the root. Any drawing must reflect this hierarchical structure, as well as any additional application-dependent constraints on the order in which children must appear. For example, family trees are rooted, with sibling nodes typically drawn from left to right in the order of birth.     
• Free trees do not encode any structure beyond their connection topology.    For example, there is no root associated with the minimum spanning tree of any graph, so a hierarchical drawing can be misleading. Such free trees might well inherit their drawing from that of the full underlying graph, such as the map of the cities whose distances define the minimum spanning tree.

Since trees are always planar graphs, they can and should be drawn such that no two edges cross.   Any of the planar drawing algorithms of Section could be used to do so. However, such algorithms are overkill, because much simpler algorithms can be used to construct planar drawings of trees. The spring-embedding heuristics of Section also work well on free trees,   although they may be too slow for many applications.

The most natural tree-drawing algorithms work with rooted trees. However, they can be used equally well with free trees by selecting one vertex to serve as the root of the drawing. This faux-root can be selected arbitrarily,   or, even better, by using a center vertex of the tree. A center vertex minimizes the maximum distance to other vertices. For trees, the center always consists of either one vertex or two adjacent vertices, so pick either one of them. Further, the center of a tree can be identified in linear time by repeatedly trimming all the leaves until only the center remains.

Your two primary options for drawing rooted trees are ranked and radial embeddings:

• Ranked embeddings - Place the root in the top center of your page, and then partition the page into the root-degree number of top-down strips.   Deleting the root creates the root-degree number of subtrees, each of which is assigned to its own strip. Draw each subtree recursively, by placing its new root (the vertex adjacent to the old root) in the center of its strip a fixed distance from the top, with a line from old root to new root. The output figure above is a nicely ranked embedding of a balanced binary tree.

  Such ranked embeddings are particularly effective for rooted trees used to represent a hierarchy, be it a family tree, a data structure, or a corporate ladder.   The top-down distance illustrates how far each node is from the root. Unfortunately, such a repeated subdivision eventually produces very narrow strips, until most of the vertices are crammed into a small region of the page. You should adjust the width of each strip to reflect the total number of nodes it will contain, or even better, the maximum number of nodes on a single level.

• Radial embeddings - A better way to draw free trees is with a radial embedding, where the root/center of the tree is placed in the center of the drawing.   The space around this center vertex is divided into angular sectors for each subtree. Although the same problem of cramping will eventually occur, radial embeddings make better use of space than ranked embeddings and appear considerably more natural for free trees. The rankings of vertices in terms of distance from the center is illustrated by the concentric circles of vertices.

Implementations: Georg Sander maintains a comprehensive WWW page on graph drawing at http://www.cs.uni-sb.de/RW/users/sander/html/gstools.html. This should probably be your first stop in hunting down programs for tree drawing.

The best FTP-able package of graph drawing algorithms is GraphEd, by Michael Himsolt (himsolt@fmi.uni-passau.de).   It contains a variety of graph and tree drawing algorithms and an interface to support user-specific extensions written in C.   See Section for more details on GraphEd and other graph drawing systems.

Combinatorica [Ski90] provides Mathematica implementations    of several tree drawing algorithms, including radial and rooted embeddings. See Section for further information on Combinatorica.

Notes: The best reference available on graph drawing is the annotated bibliography on graph drawing   algorithms by Giuseppe Di Battista, Peter Eades, and Roberto Tamassia [BETT94], also available via http://www.cs.brown.edu/ rt.

Heuristics for tree layout have been studied by several researchers [RT81, Vau80, WS79], although under certain aesthetic criteria the problem is NP-complete [SR83].  

Related Problems: Drawing graphs (see page ), planar drawings (see page ).