Study and implementation of some tree drawing algorithms

Thumbnail Image
Hussein, Iman Y.
Bagga, Jay
Issue Date
Thesis (M.S.)
Department of Computer Science
Other Identifiers

Graph drawing deals with the geometric representation of graphs [1]. Data representation problems that require graph models can be better understood when visualized with appropriate graph drawings. The typical data structure for modeling hierarchical information is a tree whose vertices represent entities and whose edges correspond to relationships between entities. Algorithms for drawing trees are typically based on some graph-theoretic insight into the structure of the tree. It is characterized by the fact that in the drawings produced, the nodes at the same distance from the root are horizontally aligned [1]. This level-based approach can be used for both binary and general trees. Algorithms based on this approach involve some issues that lead to aesthetically wider than necessary drawings. I implemented “A Naïve Tree Drawing Algorithm” [2] as part of an independent study. This will serve as a basis and an introduction to this proposed thesis. In this thesis, we develop some tree drawing algorithms and a planarity drawing algorithm in terms of constructing a new pseudocode for each algorithm. Also, we focus on the theoretical graphic insight to the structure of the tree by building a drawing application for each algorithm. These applications provide an important view of the properties of drawing trees. In addition, these algorithms are implemented in a GUI (JEdit) that reflects an efficient aesthetic drawing. The input graph is checked to verify that it is a tree. The user sees an error message otherwise. These algorithms allow the user to select the root in an input tree. This leads to a better understanding of the algorithms. Most of these algorithms calculate the levels of the tree and the number of the nodes in each level. These algorithms are : the “Recursive Algorithm for Binary Trees” from [3], which has many steps, the “A Node-Positioning Algorithm for General Trees” from [4], the “Area-Efficient Order-Preserving Planar Straight-Line Drawings of Ordered Trees” from Section 3 of [5], and “Planarity Drawing Algorithm” from Section 2 of [6].