Campus Event Calendar
Event Entry
New for: D3
What and Who
Visualizing Trees
Vincent van der Weele
Other:
Talk
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 15 April 2010
11:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
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.
Contact
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.
Frank Neumann, 04/12/2010 15:42 -- Created document.