Treemaps with bounded aspect ratio (Q2450205)

The paper deals with the problem of visualization of hierarchical data with the help of treemaps. The input for a treemap is a tree \(T\) where every leaf is associated with a weight and the weight of an internal node is the sum of the weights of its children. A treemap for \(T\) is a hierarchical partition of a simple polygon (usually a rectangle) into simply connected regions. Each region represents a node of \(T\), and the area of each region is proportional to the weight of the corresponding node. Users find it difficult to compare regions with extreme aspect ratios, so one of the most important quality criteria for treemaps is the aspect ratio of the regions. Because of this the authors concentrate on treemaps with a bounded aspect ratio. Firstly, the authors give a recursive algorithm for computing a convex treemap (treemap with polygonal partition) of aspect ratio \(O(depth(T))\) for a properly weighted tree \(T\), i.e., a tree in which each node has a positive weight and it equals the sum of the weights of its children. The algorithm consists of two phases. In the first phase \(T\) is converted into a binary tree \(T^{*}\), and in the second phase a partition of \(T^{*}\) is constructed in a top-down manner. Next, the authors introduce a recursive algorithm for computing an orthoconvex treemap of constant aspect ratio for a properly weighted binary tree. If the tree is not a binary one, they can replace each node of degree \(k > 2\) by a binary subtree with \(k-1\) new internal nodes. The partition obtained with the algorithm consists of rectangles, \(L\)-, and \(S\)-shapes of constant aspect ratio. Finally, the authors consider a special case \(depth(T) = 1\), i.e., single-level treemaps. The considerations start with proving that minimizing the aspect ratio with the restriction that the regions are rectangles is NP-hard. Then, the authors describe a drawing procedure in which the regions are allowed to be drawn as \(L\)-shapes. The proposed algorithm gives a much better bound on the aspect ratio than for the general case.