An experimental study on algorithms for drawing binary trees

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 beenfound to be the best in all categories.