$\emph{Graph drawing}$ addresses a problem of constructing graphic and geometric representations of graphs in the two-dimensional plane or three-dimensional space. In general, each vertex of a graph is represented by a geometric element such as point, box, and circle, and each edge is represented by a simple open Jordan curve between the elements associated with its both end vertices.
Graph drawing is an emerging area of research that combines flavors of topological graph theory and computational geometry. Furthermore, the graph drawing has important applications in computer science such as VLSI design, software engineering, information visualization system, database design, project management, and computer-aided-design. The usefulness of a drawing of a graph depends on its readability, which is measured by optimizing important aesthetic criteria such as the area, volume, the number of bends, and the aspect ratio.
In this thesis, we aim at developing grid and planar drawing algorithms for bounded-degree trees so that the drawings optimize aesthetic criteria as much as possible. By bounded-degree trees we mean that the degree of the trees is bounded by some positive constant. A drawing is grid and planar if all vertices are placed at distinct grid points and no two edges in the drawing intersect.
A tree is a fundamental and useful data structure that represents hierarchies of many information structures such as family charts, organization charts, and search trees. To display the hierarchy of the tree, it is natural that every edge of the tree should be vertically monotone chain from the parent to the child so that the parent has y-coordinate greater than or equal to that of its child. A drawing satisfying this standard is said to be upward. The contribution of the thesis consists of two parts; upward tree drawing algorithms and non-upward tree drawing algorithms.
All upward and non-upward drawing algorithms presented in this thesis are based on a unified drawing framework, called partition-and-merge strategy. The framework works as follows: Partition a bounded-degree tree into several pieces by deleting some edges of the tree, draw the pieces, and then merge drawings of the pieces by inserting the deleted edges. The effectiveness of the strategy heavily depends on how to partition a tree. We propose a new partitioning method that one can merge the drawing pieces with a little additional cost.
First, we investigate upward tree drawing problems for a bounded-degree tree of n vertices in the two-dimensional plane. In such upward problems, a big open question is to answer if one can draw a (bounded-degree) tree with area less than O(n log n) when each edge of the tree is drawn as a straight-line. In this thesis, we present an O(n log log n)-area upward straight-line drawing algorithm for any bounded degree tree. This is the first result admitting the area less than O(n log n). Besides the upward straight-line drawing algorithm, we present other upward drawing algorithms under various conditions where each edge is drawn as a chain of orthogonal segments or the order of children for each vertex is still preserved in the upward drawing.
Second, we present non-upward tree drawing algorithms in two and three dimension. If each edge is drawn as an orthogonal straight-line (i.e., a horizontal or a vertical segment), then we can show that any binary tree of n vertices admits a drawing whose area is O(nloglogn) and whose aspect ratio is an arbitrary value in a range of [O(1),O(n log log n/$log^2 n$)]. The aspect ratio of a drawing is defined to be the ratio of the longest side length to the shortest side length of the drawing. In addition, we can immediately extend the two-dimensional drawing to a three-dimensional O(n log log n)-volume drawing with arbitrary aspect ratio. These algorithms are all the first results to guarantee the area or volume less than O(n log n) and permit any arbitrary aspect ratio.
Our partition-and-merge strategy can be also used for producing a non-upward orthogonal drawing in which each edge is represented as a chain of orthogonal segments. In the orthogonal drawing, we focus on the aspect ratio and the number of bends per edge of the drawing. We present two- and three-dimensional drawing algorithms that generate orthogonal drawings with any arbitrary aspect ratio and the number of bends per edge less than the best one known so far, still keeping the area or volume optimal. As a result, we conclude that the partition-and-merge strategy is a unified drawing framework that gives 'good' tree drawings fulfilling various aesthetic qualities under many drawing types.
