Treemapping

In information visualization and computing, treemapping is a method for displaying hierarchical data using nested figures, usually rectangles.

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: These properties have an inverse relationship.

To cope with this problem, several algorithms have been proposed that use regions that are general convex polygons, not necessarily rectangular.

The latter two algorithms operate in two steps (greatly simplified for clarity): In convex treemaps, the aspect ratio cannot be constant - it grows with the depth of the tree.

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

The main distinguishing feature of a treemap, however, is the recursive construction that allows it to be extended to hierarchical data with any number of levels.

This idea was invented by professor Ben Shneiderman at the University of Maryland Human – Computer Interaction Lab in the early 1990s.

[21][22] Shneiderman and his collaborators then deepened the idea by introducing a variety of interactive techniques for filtering and adjusting treemaps.

Despite many desirable properties (it is stable, preserves ordering, and is easy to implement), the slice-and-dice method often produces tilings with many long, skinny rectangles.

In 1994 Mountaz Hascoet and Michel Beaudouin-Lafon invented a "squarifying" algorithm, later popularized by Jarke van Wijk, that created tilings whose rectangles were closer to square.

In 1999 Martin Wattenberg used a variation of the "squarifying" algorithm that he called "pivot and slice" to create the first Web-based treemap, the SmartMoney Map of the Market, which displayed data on hundreds of companies in the U.S. stock market.

[citation needed] In recent years, treemaps have made their way into the mainstream media, including usage by the New York Times.