ABSTRACT
Constructing geometric representations of graphs in a readable and efficient way is crucial for understanding the inherent properties of the structures in many applications. The desire to generate a layout of such representations by algorithms and not by hand meeting certain aesthetics has motivated the research area Graph Drawing. Examples of these aesthetics include minimizing the number of edge crossings, minimizing the number of edge bends, minimizing the display area of the graph, visualizing a common direction (flow) in the graph, maximizing the angular resolution at the vertices, and maximizing the display of symmetries. Certainly, two aesthetic criteria cannot be simultaneously optimized in general and it depends on the data which criterion should be preferably optimized. Graph Drawing Software relies on a variety of mathematical results in graph theory, topology, geometry, as well as computer science techniques mainly in the areas algorithms and data structures, software engineering and user interfaces. A typical graph drawing problem is to create for a graph G = (V,E) a geometric rep-
resentation where the nodes in V are drawn as geometric objects such as points or two dimensional shapes and edges (u, v) ∈ E are drawn as simple Jordan curves connecting the geometric objects associated with u and v. Apart from the, in the context of this book obvious, visualization of Data Structures, other application areas are, e.g., software engineering (Unified Modeling Language (UML), data flow diagrams, subroutine-call graphs) databases (entity-relationship diagrams), decision support systems for project management (business process management, work flow). A fundamental issue in Automatic Graph Drawing is to display trees, since trees are
a common type of data structure (Chapter 3). Thus a good drawing of a tree is often a powerful intuitive guide for analyzing data structures and debugging their implementations. It is a trivial observation that a tree T = (V,E) always admits a planar drawing, that is a drawing in the plane such that no two edges cross. Thus all algorithms that have been developed construct a planar drawing of a tree. Furthermore it is noticed that for trees the
and
condition |E| = |V | − 1 holds and therefore the time complexity of the layout algorithms is always given in dependency to the number of nodes |V | of a tree. In 1979, Wetherell and Shannon [24] presented a linear time algorithm for drawing binary
trees satisfying the following aesthetic requirements: the drawing is strictly upward, i.e. the y-coordinate of a node corresponds to its level, so that the hierarchical structure of the tree is displayed; the left child of a node is placed to the left of the right child, i.e., the order of the children is displayed; finally, each parent node is centered over its children. Moreover, edges are drawn straight line. Nevertheless, this algorithm showed some deficiencies. In 1981, Reingold and Tilford [17] improved the Wetherell-Shannon algorithm by adding the following feature: each pair of isomorphic subtrees is drawn identically up to translation, i.e., the drawing does not depend on the position of a subtree within the complete tree. They also made the algorithm symmetrical: if all orders of children in a tree are reversed, the computed drawing is the reflected original one. The width of the drawing is not always minimized subject to these conditions, but it is close to the minimum in general. The algorithm of Reingold and Tilford that runs in linear time, is given in Section 45.3. Figure 45.1 gives an example of a typical layout produced by Reingold and Tilford’s algorithm.
