Study and implementation of some tree drawing algorithms

Cardinal Scholar

Show simple item record

dc.contributor.advisor Bagga, Jay
dc.contributor.author Hussein, Iman Y.
dc.date.accessioned 2017-07-17T12:43:57Z
dc.date.available 2017-07-17T12:43:57Z
dc.date.issued 2017-07-22
dc.identifier.uri http://cardinalscholar.bsu.edu/handle/123456789/200799
dc.description.abstract 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]. en_US
dc.description.sponsorship Department of Computer Science
dc.description.tableofcontents Graph drawing basics and (GUI) for graph theory -- A naive tree drawing algorithm -- Recursive algorithm for binary trees -- A node positioning algorithm for general trees -- Area-efficient order-preserving planar straight-line drawings of ordered trees -- Planarity drawing algorithm.
dc.subject.lcsh Trees (Graph theory) -- Computer programs.
dc.subject.lcsh Graph algorithms.
dc.subject.other Jedit (Computer program)
dc.title Study and implementation of some tree drawing algorithms en_US
dc.description.degree Thesis (M.S.) en_US
dc.identifier.cardcat-url http://liblink.bsu.edu/uhtbin/catkey/1863889


Files in this item

This item appears in the following Collection(s)

  • Master's Theses [5256]
    Master's theses submitted to the Graduate School by Ball State University master's degree candidates in partial fulfillment of degree requirements.

Show simple item record

Search Cardinal Scholar


Browse

My Account