In information visualization and computing, treemapping is a method for displaying hierarchical data using nested figures, usually rectangles.
1 Main idea 2 Tiling algorithms 3 Rectangular treemaps 4 Convex treemaps
5 Other treemaps 6 History 7 See also 8 References 9 External links
Main idea Treemaps display hierarchical (tree-structured) data as a set of nested rectangles. Each branch of the tree is given a rectangle, which is then tiled with smaller rectangles representing sub-branches. A leaf node's rectangle has an area proportional to a specified dimension of the data. Often the leaf nodes are colored to show a separate dimension of the data. When the color and size dimensions are correlated in some way with the tree structure, one can often easily see patterns that would be difficult to spot in other ways, such as if a certain color is particularly relevant. A second advantage of treemaps is that, by construction, they make efficient use of space. As a result, they can legibly display thousands of items on the screen simultaneously. Tiling algorithms To create a treemap, one must define a tiling algorithm, that is, a way to divide a region into sub-regions of specified areas. Ideally, a treemap algorithm would create regions that satisfy the following criteria:
A small aspect ratio - ideally close to one. Regions with a small aspect ratio (i.e, fat objects) are easier to perceive. Preserve some sense of the ordering in the input data. Change to reflect changes in the underlying data.
Unfortunately, these properties have an inverse relationship. As the aspect ratio is optimized, the order of placement becomes less predictable. As the order becomes more stable, the aspect ratio is degraded.[example needed] Rectangular treemaps To date, six primary rectangular treemap algorithms have been developed:
Algorithm Order Aspect ratios Stability
BinaryTree partially ordered high stable
Mixed Treemaps ordered lowest stable
Ordered and Quantum partially ordered medium medium stability
Slice And Dice ordered very high stable
Squarified unordered[further explanation needed] lowest medium stability
Strip ordered medium medium stability
Convex treemaps Rectangular treemaps have the disadvantage that their aspect ratio might be arbitrarily high in the worst case. As a simple example, if the tree root has only two children, one with weight
and one with weight
1 − 1
, then the aspect ratio of the smaller child will be
, which can be arbitrarily high. To cope with this problem, several algorithms have been proposed that use regions that are general convex polygons, not necessarily rectangular. Convex treemaps were developed in several steps, each step improved the upper bound on the aspect ratio. The bounds are given as a function of
- the total number of nodes in the tree, and
- the total depth of the tree. 1. Onak and Sidiropoulos proved an upper bound of
O ( ( d log
displaystyle O((dlog n )^ 17 )
. 2. De-Berg and Onak and Sidiropoulos improve the upper bound to
O ( d + log
displaystyle O(d+log n )
, and prove a lower bound of
Ω ( d )
displaystyle Omega (d)
. 3. De-Berg and Speckmann and van-der-Weele improve the upper bound to
O ( d )
, matching the theoretical lower bound.
For the special case where the depth is 1, they present an algorithm that uses only four classes of 45-degree-polygons (rectangles, right-angled triangles, right-angled trapezoids and 45-degree pentagons), and guarantees an aspect ratio of at most 34/7.
The latter two algorithms operate in two steps (greatly simplified for clarity):
A. The original tree is converted to a binary tree: each node with more than two children is replaced by a sub-tree in which each node has exactly two children. B. Each region representing a node (starting from the root) is divided to two, using a line that keeps the angles between edges as large as possible. It is possible to prove that, if all edges of a convex polygon are separated by an angle of at least
, then its aspect ratio is
O ( 1
displaystyle O(1/phi )
. It is possible to ensure that, in a tree of depth
, the angle is divided by a factor of at most
, hence the aspect ratio guarantee.
For the special case where the depth is 1, they present an algorithm that uses only rectangles and L-shapes, and the aspect ratio is at most
2 + 2
displaystyle 2+2/ sqrt 3 approx 3.15
; the internal nodes use only rectangles with aspect ratio at most
displaystyle 1+ sqrt 3 approx 2.73
Voronoi Treemaps - based on
Treemap of Benin's exports by product category, 2009. The Product Exports Treemaps are one of the most recent applications of these kind of visualizations, developed by the Harvard-MIT Observatory of Economic Complexity
Disk space analyzer Information visualization List of countries by economic complexity, which includes a list of Products Exports Treemaps. Marimekko Chart, a similar concept with one level of explicit hierarchy.
^ Kong, N; Heer, J; Agrawala, M (2010). "Perceptual Guidelines for Creating Rectangular Treemaps". IEEE Transactions on Visualization and Computer Graphics. 16 (6): 990. doi:10.1109/TVCG.2010.186. PMID 20975136. ^ a b Ben Shneiderman; Catherine Plaisant (June 25, 2009). "Treemaps for space-constrained visualization of hierarchies ~ Including the History of Treemap Research at the University of Maryland". Retrieved February 23, 2010. ^ Roel Vliegen; Erik-Jan van der Linden; Jarke J. van Wijk. "Visualizing Business Data with Generalized Treemaps" (PDF). Retrieved February 24, 2010. ^ Bederson, Benjamin B.; Shneiderman, Ben; Wattenberg, Martin (2002). "Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies". ACM Transactions on Graphics. 21 (4): 833. doi:10.1145/571647.571649. ^ Bruls, Mark; Huizing, Kees; van Wijk, Jarke J. (2000). "Squarified treemaps". In de Leeuw, W.; van Liere, R. Data Visualization 2000: Proc. Joint Eurographics and IEEE TCVG Symp. on Visualization (PDF). Springer-Verlag. pp. 33–42 inconsistent citations . ^ Krzysztof Onak; Anastasios Sidiropoulos. "Circular Partitions with Applications to Visualization and Embeddings". Retrieved June 26, 2011. ^ Mark de Berg; Onak, Krzysztof; Sidiropoulos, Anastasios (2010). "Fat Polygonal Partitions with Applications to Visualization and Embeddings". arXiv:1009.1866 [cs.CG]. ^ a b De Berg, Mark; Speckmann, Bettina; Van Der Weele, Vincent (2014). "Treemaps with bounded aspect ratio". Computational Geometry. 47 (6): 683. arXiv:1012.1749 . doi:10.1016/j.comgeo.2013.12.008. . Conference version: Convex Treemaps with Bounded Aspect Ratio (PDF). EuroCG. 2011. ^ Balzer, Michael; Deussen, Oliver (2005). "Voronoi Treemaps". In Stasko, John T.; Ward, Matthew O. IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 October 2005, Minneapolis, MN, USA (PDF). IEEE Computer Society. p. 7. . ^ Wattenberg, Martin (2005). "A Note on Space-Filling Visualizations and Space-Filling Curves". In Stasko, John T.; Ward, Matthew O. IEEE Symposium on Information Visualization (InfoVis 2005), 23-25 October 2005, Minneapolis, MN, USA (PDF). IEEE Computer Society. p. 24. . ^ Auber, David; Huet, Charles; Lambert, Antoine; Renoust, Benjamin; Sallaberry, Arnaud; Saulnier, Agnes (2013). "Gosper Map: Using a Gosper Curve for laying out hierarchical data". IEEE Transactions on Visualization and Computer Graphics. 19 (11): 1820–1832. doi:10.1109/TVCG.2013.91. PMID 24029903. . ^ Shneiderman, Ben (1992). "Tree visualization with tree-maps: 2-d space-filling approach". ACM Transactions on Graphics. 11: 92. doi:10.1145/102377.115768. ^ Cox, Amanda; Fairfield, Hannah (February 25, 2007). "The health of the car, van, SUV, and truck market". The New York Times. Retrieved March 12, 2010. ^ Carter, Shan; Cox, Amanda (February 14, 2011). "Obama's 2012 Budget Proposal: How $3.7 Trillion is Spent". The New York Times. Retrieved February 15, 2011.
Wikimedia Commons has media related to Treemaps.
Treemap Art Project produced exhibit for the National Academies in
An article by
v t e
Visualization of technical information
Biological data visualization
Chart Diagram Engineering drawing Graph of a function Ideogram Map Photograph Pictogram Plot Schematic Statistical graphics Table Technical drawings Technical illustration User interface
Jacques Bertin Stuart Card Thomas A. DeFanti Michael Friendly George Furnas Pat Hanrahan Nigel Holmes Christopher R. Johnson Manuel Lima Alan MacEachren Jock D. Mackinlay Michael Maltz Bruce H. McCormick Miriah Meyer Charles Joseph Minard Rudolf Modley Gaspard Monge Tamara Munzner Otto Neurath Florence Nightingale Hanspeter Pfister Clifford A. Pickover William Playfair Karl Wilhelm Pohlke Adolphe Quetelet George G. Robertson Arthur H. Robinson Lawrence J. Rosenblum Ben Shneiderman Edward Tufte Fernanda Viégas Ade Olufeko Howard Wainer Martin Wattenberg Bang Wong
Cartography Chartjunk Computer graphics
in computer science
Graph drawing Graphic design Graphic organizer Imaging science Information graphics Information science Mental visualisation Misleading graph Neuroimaging Patent drawing Scientific modelling Spatial analysis Visual analytics Visual perception Volume cartography Volu