Campus Event Calendar

Event Entry

New for: D3

What and Who

Visualizing Trees

Vincent van der Weele
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS  
AG Audience

Date, Time and Location

Thursday, 15 April 2010
30 Minutes
E1 4


Trees can be visualized in many ways. If each leaf has a certain weight, and the weight of a tree is the sum of the weights of its subtrees, a tree-map can be a useful visualization. In a tree-map, a tree is represented by a rectangle. This rectangle is partitioned in a number of smaller rectangles, one for each subtree, such that the area of each rectangle is proportional to the weight of its corresponding subtree. This approach is repeated recursively, until each leaf is represented by a rectangle having area proportional to its weight.

Tree-maps are first mentioned by Shneiderman, who gives a simple slice-and-dice algorithm to compute a tree-map. However, the aspect ratio - measuring if a rectangle is close to square - can be very poor in this method. Heuristic-based methods have been developed to overcome this issue, but without guarantees on the maximal aspect ratio.

We look into aspect ratio optimization in trees of height one - consisting of a root and a number of leaves. We try to prove NP-hardness of the general problem and give solutions to guarantee a constant aspect ratio for the special cases that all leaf weights are in a certain range and that shapes other than rectangles are allowed.


Frank Neumann
--email hidden
passcode not visible
logged in users only

Frank Neumann, 04/12/2010 15:42
Frank Neumann, 04/12/2010 15:42 -- Created document.