Graph Drawing And Its Performance Of Binary Trees

This paper studies graph drawings of binary trees. It is divided into three parts.The first section briefly describes the background knowledge of graph drawings, the current research and the prior knowledge, which include the representation of graph, aesthetic standards, the definition of tree, drawing methods and its utility analysis. This section also shows the main research results of this paper.The second section gives the mathematical definitions and the decision version of minimizing the width of binary tree which has been given height restriction and should be draw in strictly up, straight line, and on grid. We prove the problem is NP. This section also gives the enumeration method of solving the problem and two heuristic algorithms-greedy algorithm and neighborhood search algorithm. Then we prove the time complexity of enumeration is the time complexity of greedy algorithm is O(n2h), as well as the time complexity of neighborhood search algorithm.The third section examines the range of studies from general binary trees to complete binary trees, and gives a2-approximation algorithm of minimizing the width of complete binary trees which has been given height restriction and should be draw in strictly up, straight line, and on grid through the perspective of different heights. Then we improve the2-approximation algorithm and get a nested loop algorithm. The improved algorithm is also a2-approximation algorithm.