Ordered Treemap Layouts
=======================

Slice-and-dice creates long, thin rectangles.

Clustered algorithms and squarified algorithms try to make aspect ratio near 1.

But: layout changes abruptly when data changes (hinders reading, selection,
comparison, and recall).  Ordering is no longer preserved.

Just eliminate the sorting step.

Ordered Algorithm
-----------------

Choose a pivot element, P.

Place rectangle R_P along top or left side, whichever is longest.

Place items ordered before P in rectangle R_1 (above P).
Place items after P in R_2 (to the right of P), R_3 (below P)
to optimize aspect of R_P.

Recurse on R_1, R_2, R_3.

.----------------.
|                |
|                |
|                |
|      R_1       |
|                |
|                |
|                |
|                |
|----------------|
|      |         |
| R_P  |   R_2   |
|      |         |
|----------------|
|                |
|                |
|      R_3       |
|                |
|                |
.----------------.


Strip Treemap Algorithm
-----------------------

Arrange items in horizontal strips.

Goal is low average aspect ratio, not uniform strip height.

How to choose pivot?
--------------------

Choose largest item.

Choose middle-sized item.

Choose so that groups of items before and after
pivot are roughly the same size.

Choices: slice-and-dice; pivot by middle; pivot by split size;
strip treemap; cluster; squarified.

Evaluation
----------

Consider: *aspect ratio* (average for all leaf rectangles, using
max(w, h)/min(w, h)); *change* (rectangle = (x, y, w, h), use
Euclidean distance in R^4); *disorder* (draw a sequence of line
segments connecting rectangles in order and measure percentage
of instances where line segments change direction).

Slice-and-dice has bad aspect, good ordering.

Squarified and clustered have good aspect, bad ordering.

Strip treemaps are a good compromise.

Measures of disorder correlate well to reaction times for selection
tested on people.

Mixed Layouts
-------------

Use different layouts at different levels.

At top level, use most stable; at leaf nodes, optimize aspect ratio.