ABSTRACT
Tree drawing is concerned with the automatic generation of geometric representations of relational information, often for visualization purposes. The typical data structure for modeling hierarchical information is a tree whose vertices represent entities and whose edges correspond to relationships between entities. Visualizations of hierarchical structures are only useful to the degree that the associated diagrams effectively convey information to the people that use them. A good diagram helps the reader understand the system, but a poor diagram can be confusing. The automatic generation of drawings of trees finds many applications, such as software
engineering (program nesting trees, object-oriented class hierarchies), business administration (organization charts), decision support systems (activity trees), artificial intelligence (knowledge-representation isa hierarchies), logic programming (SLD-trees), website design and browsing (structure of a website), biology (evolutionary trees), and chemistry (molecular drawings). Algorithms for drawing trees are typically based on some graph-theoretic insight into the
structure of the tree. The input to a tree drawing algorithm is a tree T that needs to be drawn. The output is a drawing Γ, which maps each node of T to a distinct point in the plane, and each edge (u, v) of T to a simple Jordan curve with endpoints u and v. T is an ordered tree if the children of each node are assigned a fixed left-to-right order.
For any node u in T , its leftmost child (rightmost child) is the one that comes first (last) in the left-to-right ordering of the children of u in T . The leftmost path p of T is the maximal path consisting of nodes that are leftmost children, except the first one, which is the root
of T . The last node of p is called the leftmost node of T . Two nodes of T are siblings if they have the same parent. The subtree of T rooted at a node v consists of v and all the descendants of v. T is the empty tree if it has zero nodes in it.
