A New Heuristic Algorithm for Drawing Binary Trees within Arbitrary Polygons Based on Center of Gravity

Graphs have enormous usage in software engineering, network and electrical engineering. In fact graphs drawing is a geometrically representation of information. Among graphs, trees are concentrated because of their ability in hierarchical extension as well as processing VLSI circuit. Many algorithms have been proposed for drawing binary trees within polygons. However these algorithms generate binary trees with edge intersections and bends. Likewise, they have limitations in drawing binary trees in any arbitrary polygon with uniform distribution. The proposed algorithm which is based on calculating center of gravity in polygons draws a binary tree inside any kinds of polygon. besides center of gravity as a heuristic the segmentation process has already been used. The results which have been implemented with Microsoft Visual Basic reveal that the proposed heuristic algorithm had no edge intersection and no bend. In addition, not only the symmetry of drawing has been improved but also the computational complexity becomes less.

کلیدواژه ها:

Binary Tree ، Polygon ، Edge Intersection ، Bend