EDGE-EQUALIZED TREEMAPS - Information Visualisation: Techniques, Usability and Evaluation - page 119

and vertical directions in this problem, and place the child node rectangles
from left to right in the fixed-height rectangle.
In our problem, the height of the rectangle into which the child nodes
will be placed is unknown. Therefore, we fit the rectangles of the child
nodes while slowly adjusting the height parameter. We use two algorithms
as solutions to the Strip Packing Problem. One of them is the Next-Fit
Algorithm [11], which is a solution to the Bin Packing Problem (Fig. 6.7).
If the order of placement of the rectangles has been decided, the Next-Fit
Algorithm offers a high-speed layout solution. In this algorithm, rectangles
are filled from the upper left to the lower right of the Treemap. The
algorithm places rectangles from top to bottom; if it cannot place a
rectangle at the bottom, it draws a line on the right and continues placing
rectangles on the line from the top. By repeatedly changing the placing
order, we can adopt the best result.
Fig. 6.7. Placement using the Next-Fit Algorithm
We also use the Stack Algorithm (Fig. 6.8). This assumes that the
rectangle widths are equal. This algorithm sorts rectangles in descending
order; the rectangles are then placed in order, from the smallest rectangle
at the top of the largest rectangle. Because this algorithm does not depend
on the placing order of the rectangles, it can be faster than the Next-Fit
Algorithm.
Fig. 6.8. Placement using the Stack Algorithm
Determination of rectangles for branch nodes: The dimensions of each
branch node are determined by the result of the placement of child nodes.