Grid Drawings of Binary Trees: An Experimental Study

Abstract

In this paper we consider the class of binary trees and present the results of a comprehensive experimental study on the four most representative algorithms for drawing trees, one for each of the following tree-drawing approaches: Separation-Based, Path-based, Level-based, and Ringed Circular Layout. We establish a simpler, more intuitive format for storing binary trees in files and create a large suite of randomly-generated, unbalanced, complete, AVL, Fibonacci, and molecular combinatory binary trees of various sizes. Our study is therefore conducted on randomly-generated, unbalanced, and AVL binary trees with between 100 and 50,000 nodes, on Fibonacci trees T_n for n=1,2,...,45,46 (143 to 46,367 nodes), on complete binary trees of size 2ⁿ−1 for n=7,8,...,15,16 (127 to 65,535 nodes), and on molecular combinatory binary trees with between 133 and 50,005 nodes. Our study yields 70 charts comparing the performance of the drawing algorithms with respect to ten quality measures, namely Area, Aspect Ratio, Size, Total Edge Length, Average Edge Length, Maximum Edge Length, Uniform Edge Length, Angular Resolution, Closest Leaf, and Farthest Leaf. None of the algorithms has been found to be the best in all categories. This observation leads us to create an adaptive system that determines the type of a binary tree and then selects an algorithm to draw the tree depending upon the specified quality measures. Currently, our adaptive tree drawing system recognizes all six types of binary trees and all ten measures included in our experimental study. Under our settings, our adaptive tree drawing system outperforms any system using a single binary tree drawing algorithm.