Tree drawing using partition-and-merge strategy in two and three dimensions

Abstract

$\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 uni...