An experimental study on algorithms for drawing binary trees

ABSTRACT

In this paper we present the results of a comprehensive experimental study on the four most representative algorithms for drawing binary trees without distorting or occluding the information, one for each of the following distinct tree-drawing approaches: Separation-Based approach (Garg & Rusu 2003), Path-Based approach (Chan, Goodrich, Rao Kosaraju & Tamassia 2002), Level-Based approach (Reingold & Tilford 1981), and Ringed Circular Layout approach (Teoh & Ma 2002).Our study is conducted on randomly-generated, unbalanced, and AVL binary trees with up to 50,000 nodes, on Fibonacci trees with up to 46,367 nodes, on complete trees with up to 65,535 nodes, and on real-life molecular combinatory binary trees with up to 50,005 nodes. We compare the performance of the drawing algorithms with respect to five quality measures, namely Area, Aspect Ratio, Uniform Edge Length, Angular Resolution, and Farthest Leaf. None of the algorithms have been found to be the best in all categories.

REFERENCES

• 1: Timothy M. Chan , Michael T. Goodrich , S. Rao Kosaraju , Roberto Tamassia, Optimizing area and aspect ratio in straight-line orthogonal tree drawings, Computational Geometry: Theory and Applications, v.23 n.2, p.153-162, September 2002 [doi>10.1016/S0925-7721(01)00066-9]
• 2: G. Di Battista, P. Eades, R. Tamassia, & I. G. Tollis. (1999), Graph Drawing, Prentice Hall, Upper Saddle River, NJ.
• 3: A. Garg & A. Rusu. (2003), A more practical algorithm for drawing binary trees in linear area with arbitrary aspect ratio, in Proceedings 11th International Symposium on Graph Drawing, volume 2912 of Lecture Notes Comput. Sci., pages 159-165, Springer.
• 4: B. MacLennan. (2003), Molecular Combinatory Computing for Nanostructure Synthesis and Control, in Proceedings 3rd IEEE Conference on Nanotechnology , IEEE Press, pp. 179-182 vol. 2.
• 5: E. Reingold & J. Tilford. (1981), Tidier drawings of trees, in IEEE Transactions on Software Engineering , 7(2):223-228.
• 6: A. Rusu, R. Jianu, C. Santiago, & C. Clement. (2005), Planar Straight-Line Grid Drawings of Binary Trees: An Experimental Study, Technical Report 2005-01, Department of Computer Science, Rowan University, Glassboro, NJ.
• 7: A. Rusu, C. Clement, & R. Jianu. (2005), Performance Analysis of a Path-Based Algorithm for Drawing Binary Trees, in Proc. 5th International Conference on Artificial Intelligence and Digital Communications, Research Notes in Computer Science, pages 84-102.
• 8: Soon Tee Teoh , Kwan-Liu Ma, RINGS: A Technique for Visualizing Large Hierarchies, Revised Papers from the 10th International Symposium on Graph Drawing, p.268-275, August 26-28, 2002
• 9: L. Valiant. (1981), Universality considerations in VLSI circuits, in IEEE Trans. Comput., C-30(2):135-140.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms, Design

Keywords:
binary trees, drawing algorithm, experimental study, planar, straight-line