latexYou have requested package latexYou have requested document class
captionUnknown document class hyperrefToken not allowed in a PDF string
(PDFDocEncoding)  newfloatplacementnewfloatnamenewfloatfileextnewfloatwithin

# Space Partitioning Schemes and Algorithms for Generating Regular and Spiral
Treemaps

Mehdi Behroozi  $|$ , Reyhaneh Mohammadi  $|$ , and Cody Dunne  $|$ Mehdi
Behroozi is the corresponding author. All authors are with Northeastern
University, Boston, MA, USA. E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>A full version of this
paper with all appendices and data sets is available at osf.io (hyperlink).

###### Abstract

Treemaps have been widely applied to the visualization of hierarchical data. A
treemap takes a weighted tree and visualizes its leaves in a nested planar
geometric shape, with sub-regions partitioned such that each sub-region has an
area proportional to the weight of its associated leaf nodes. Efficiently
generating visually appealing treemaps that also satisfy other quality
criteria is an interesting problem that has been tackled from many directions.
We present an optimization model and five new algorithms for this problem,
including two divide and conquer approaches and three spiral treemap
algorithms. Our optimization model is able to generate superior treemaps that
could serve as a benchmark for comparing the quality of more computationally
efficient algorithms. Our divide and conquer and spiral algorithms either
improve the performance of their existing counterparts with respect to aspect
ratio and stability or perform competitively. Our spiral algorithms also
expand their applicability to a wider range of input scenarios. Four of these
algorithms are computationally efficient as well with quasilinear running
times and the last algorithm achieves a cubic running time. A full version of
this paper with all appendices, data, and source codes is available at osf.io
(hyperlink).

###### Index Terms:

Regular and Spiral Treemaps, Space Partitioning Optimization, Data
Visualization, Computational Geometry

##  1 Introduction

Treemaps are well-known planar structures for visualization of tree-structured
hierarchical data with a space-filling approach. A nested treemap maps the
nodes of a tree to a nested non-overlapping structure made up with simply
connected planar figures, usually rectangles or convex polygons, where the
areas of these figures are proportionate to some attribute of the nodes of the
tree. Another way of looking at treemap layouts is that they partition a given
planar region into a number of sub-regions with given areas.

Treemaps were introduced by Shneiderman in 1991 as a space-filling technique
to visualize space usage within computer directory structures [1, 2]. Fig. 1
shows an example of tree-structured data and an associated treemap generated
with the original Slice-and-Dice algorithm. Shneiderman’s approach was to make
a rectangular treemap, in which a rectangle was recursively divided with
alternating horizontal and vertical cuts into rectangular sub-regions. Slice-
and-Dice is simple to implement, but suffers some issues particularly with
creating long and skinny rectangles. The poor aspect ratio raises issues with
interpreting any associated visual encodings [3].

Over the years several treemap variants have been proposed. These include
polygonal treemaps where the sub-regions are simple polygons [4], convex
treemaps where the sub-regions are convex polygons [5], Voronoi treemaps where
the sub-regions are Voronoi cells [6, 7], cascaded treemaps where the sub-
regions are cascaded as opposed to be nested [8], spiral treemaps where layout
presents a spiral structure [9, 10], and treemaps with space-filling fractal-
like curves such as Gosper [11] and Hilbert curves [12].

Treemaps are used in a wide range of application domains including software
visualization; file/directory structures; news and multimedia visualization;
and visualization of financial data such as stocks, budgets, and import/export
trades. Its associated spatial partitioning problem also has a wide range of
applications such as designing service districts, land allocation in farming
reforms, and matrix multiplication algorithms in parallel computing. Beyond
area encoding, treemaps can be enhanced to encode additional attributes using
color, shade, filling pattern, label, and nesting/cascading structure.
Creative and new applications of treemaps for different visualization purposes
are continuously being proposed using a variety of treemap algorithms (see
[13] for a survey on treemap algorithms).

A regular treemapping problem with rectangular sub-regions could be defined as
follows. Given a rectangle $R$ with $\mathop{\rm Area}\nolimits(R)=A$ and a
hierarchical list of areas $A_{1},...,A_{n}$ with $\sum_{i=1}^{n}A_{i}=A$
arranged in a tree data structure $T$ we want to layout $n$ non-overlapping
rectangles with areas $A_{1},...,A_{n}$ inside $R$ in a nested way that
follows the structure of $T$ and the resulting rectangles are as square as
possible with $\cup_{i=1}^{n}R_{i}=R$. The squareness of the rectangles is
important practically and aesthetically in data visualization. In this paper,
we also study another variant of this problem, where we relax the partitioning
condition ($\cup_{i=1}^{n}R_{i}=R$) and instead require the layout to follow
certain _spiral_ patterns. In other words, for regular treemaps we are given
an input region while for the spiral treemaps, there is no input region and
instead we aim to form a spiral structure with rectangular sub-regions of
given areas. For regular treemaps we propose an optimization model, one divide
& conquer algorithm, and one dynamic programming algorithm and for the spiral
treemaps we propose three constructive algorithms that mimic the “golden
spiral” structure in different ways. Our divide and conquer and dynamic
programming algorithms take a _subdivision_ approach and our spiral algorithms
take a _packing_ approach, while all proposed algorithms fall under _space-
filling_ treemaps according to the existing design space categories [14, 15,
13].

### Contributions, Outline, and Supplemental Materials

In this paper, we consider nested rectangular, convex, and spiral treemaps.
Our main contributions, listed in presentation order, are:

  1. (1)

A treemap optimization model that minimizes the total perimeter of the
component rectangles, thus favoring square sub-regions (Section 3). To the
best of our knowledge, this is the most comprehensive model in the literature
of the rectangular treemapping problem, incorporating several variants of the
problem.

  2. (2)

Two subdivision treemap algorithms based on divide & conquer and dynamic
programming that resolve the shortcoming of the prior divide & conquer
approach when faced with uneven area distributions (Section 4).

  3. (3)

Three spiral treemap algorithms that mimic the Symmetric Spirals that are
ubiquitous in nature and famous for their visual attractiveness (Section 5).
Spiral algorithm _construct_ treemaps independent of the input region.
Removing this restriction can lead to both significant improvements or
deterioration depending on the problem instance.

  4. (4)

The usage of Hausdorff distance as a metric for stability is established for
the first time.

  5. (5)

A performance comparison of treemap algorithms based on aspect ratio and
stability (Section 6). We demonstrate that our optimization model generates
superior treemaps and could serve as a benchmark for assessing more
computationally efficient approaches. Also, our other treemap algorithms offer
improved aspect ratio vs. prior methods, while staying competitive on
stability. Finally, usage examples on several diverse datasets (Section 7) are
also provided for further comparison of output visualizations.

A full version of this paper with all appendices, data, and source code is
available at osf.io (hyperlink).

##  2 Background

###  2.1 Notational Conventions

The following notational conventions are assumed throughout this paper: By
bounding box (rectangle) of a region $C$, we mean minimum-area axis-aligned
bounding box (rectangle) of $C$ and we show it with $\Box(C)$. The width and
height of a region $C$ are defined as the width and height of $\Box(C)$ and
are denoted by $\mathop{\rm width}(C)$ and $\mathop{\rm height}(C)$.
$\mathop{\rm Area}\nolimits(C)$ denotes the area of a region $C$ and
$\mathop{\rm Perim}(C)$ shows its perimeter. We define the perimeter of a
rectangle $R$ by $\mathop{\rm Perim}(R)=\mathop{\rm width}(R)+\mathop{\rm
height}(R)$. We also define the aspect ratio of a rectangle $R$ as

$\mathop{\rm AR}(R)=\max\left\\{\frac{\mathop{\rm width}(R)}{\mathop{\rm
height}(R)},\frac{\mathop{\rm height}(R)}{\mathop{\rm width}(R)}\right\\},$

i.e., $\mathop{\rm AR}\geq 1$ and the aspect ratio of a square is one. We
define the aspect ratio of a non-rectangular polygon $P$ as the aspect ratio
of its bounding rectangle $\Box(P)$. Finally, $\left|S\right|$ shows the
cardinality (size) of set $S$.

(a)

(b)

Figure 1: Hierarchical data 1(a) modeled as a height-3 weighted tree & 1(b)
the associated treemap visualization produced by Shneiderman’s original Slice-
and-Dice algorithm [1, 2].

###  2.2 Evaluation Criteria

Depending on the application area, the goal in generating a treemap and thus
the evaluation metrics for the results could be different. Generally, the
utility of a treemap-generating algorithm for decision-makers could be
evaluated according to the following metrics:

Space-filling—The main goal of most treemap algorithms is to present
information in a 2D space in an efficient, space-filling way and minimize
unused space [16]. This enables the presentation of a lot of information in a
concise format. The goal in some other treemap algorithms is to show
_containment_ between parents and children nodes where unused spaces can be
present. Here, we only consider space-filling treemaps.

Aspect ratio—Treemap algorithms should avoid generating thin and elongated
sub-regions as much as possible. A planar geometric shape is called “ _fat_ ”
if the aspect ratio of its bounding rectangle is one or close to one (almost
square). Using convex or rectangular fat shapes for a treemap collectively
forms a visually appealing pattern, makes mouse selection easier [17, 18],
allows larger labels, and can make area comparison tasks more accurate [3].
Treemap algorithms have often been designed or evaluated in terms of their
ability to minimize both maximum and average aspect ratio ($\mathop{\rm AR}$)
of the sub-regions, e.g., Squarified by Bruls et al. [17]. In Section 5 we
further discuss the experiments of Kong et al. [3]—including their finding
that both perfect squares and rectangles with extreme aspect ratios can create
misjudgment in area comparison tasks.

Stable—In many applications, the data of interest may change frequently or on
a dynamic basis. Thus stability in the face of dynamically changing data is
desired so that changes to the layout are minimal if the data is just slightly
perturbed [19, 20]. This helps the user to track what has changed without
completely distorting their mental map, as defined by Misue et al. [21]. To
measure stability we need a distance measure for corresponding pairs of sub-
regions between two layouts to measure the change in location of a sub-region
in different treemap layouts, generated after perturbation of areas. Several
such measures have been used for treemaps that can be categorized as: (1)
_absolute_ metrics that measure how much individual rectangles move/change
(e.g., _average Euclidean distance change_ (between corners) [19, 22]
_location drift_ [12], _corner travel distance_ [23]), and (2) _relative_
metrics that measure how much positions of pairs of rectangles change relative
to each other, usually by comparing their centers or aspect ratios (e.g.,
_average Euclidean distance change_ (between centroids) [24, 25], _average
angular displacement_ [24], _relative direction change_ [26], _relative
position change_ [27], and _average aspect ratio change_ and _relative parent
change_ [28]). Some of these measures fail or perform poorly for certain
cases. For example, two skinny rectangles can form a cross (which shows a
significant move of the corners and edges), while having the same centers.

Here we establish the maximum and average _Hausdorff distance_ ($\mathop{\rm
HD}$) as our metrics for stability. We define the _Hausdorff distance_ between
two compact sets $S_{1}$ and $S_{2}$, both in the same metric space, as

$\mathop{\rm HD}(S_{1},S_{2})=\max\left\\{\,\sup_{x\in S_{1}}\inf_{y\in
S_{2}}\|x-y\|,\,\sup_{y\in S_{2}}\inf_{x\in S_{1}}\|x-y\|\,\right\\},$

where $\|\cdot\|$ is the Euclidean norm, $\sup$ is the supremum and $\inf$ the
infimum. This is illustrated in Fig. 2. HD provides a measure of distance
between two corresponding sub-regions in two layouts. It shows the maximum of
the maximum distances of each sub-region in one layout to the nearest point of
its corresponding sub-region in the other layout. This is the first use of
this stability measure for treemaps and it is an absolute metric in the same
spirit of the Euclidean distance change metric proposed by Shneiderman &
Wattenberg [19].

Ordered—Preserving an input order in the output can help with recognizing the
tree structure and any hierarchy more quickly, as well as increasing the
readability and scannablity of individual items [19]. A treemap is “ _ordered_
” if its sub-regions are scannable in close to the same order as was given.
The essentiality of preserving order as a desired property depends on the
application domain. For example, it is faster to find a node with a given
label if the nodes are ordered alphabetically, or faster to find bonds that
are paying out soon if they are ordered by maturity date. We leave generating
ordered treemaps as a future research direction for the algorithms developed
in this paper.

Encoding Multivariate Data—Conveying maximum information through size, color,
shade, placement location, adjacency relations, label, filling pattern, and
nesting structure of the layout can enhance the utilization of treemaps [29].
Most algorithms could be easily enhanced with respect to this metric with some
simple modifications. But these are outside of the focus of this paper.

Here we focus solely on the first three metrics for treemaps: space-filling,
low aspect ratio, and stable. For a survey on user studies on the
effectiveness of treemaps see [30].

Figure 2:  The Hausdorff distance between rectangles $R$ & $R^{\prime}$ is
defined as $\mathop{\rm HD}(R,R^{\prime})=\max(d_{1},d_{2})$, where $d_{1}$ is
the largest Euclidean distance of a point in $R$ to its closest point in
$R^{\prime}$ and $d_{2}$ is the largest Euclidean distance of a point in
$R^{\prime}$ to its closest point in $R$.

###  2.3 Treemap Algorithms

The first treemap algorithm (and the visualization approach in general) was
developed by Shneiderman [1, 2]. His Slice-and-Dice algorithm performs an
alternating sequence of vertical and horizontal cuts. Recursively, the
direction of the layout for each level of the tree is reversed with cuts
vertically at even levels and horizontally at odd levels. If the tree has only
one level other than the root then all cuts will be vertical. This creates the
so-called slices and dices. An example of Slice-and-Dice is shown in Fig.
1(b). However, Slice-and-Dice is prone to generating thin, “skinny” rectangles
which do poorly on our aspect ratio criteria.

####  2.3.1 Aspect Ratio Optimization

Wattenberg’s Cluster algorithm [22] was the first to address aspect ratio.
Cluster was presented as a modification of Slice-and-Dice that avoids high-
aspect-ratio rectangles by employing both vertical and horizontal partitions
at each level of hierarchy and clustering similar rectangles adjacent or close
to each other. Wattenberg used Cluster for what was likely the first stock
market treemap [31].

The Squarified algorithm by Bruls et al. [17] similarly focused on generating
sub-regions that are as close as possible to squares. It takes an input
rectangle and the desired areas of sub-rectangles. First, the desired areas
are sorted in descending order. Then, in each iteration the algorithm places
rectangles either vertically or horizontally according to a subset of areas
from the sorted list. The subset is selected depending on the width and height
of the remaining area of the input rectangle and such that the maximum aspect
ratio of rectangles in this subset is minimized. Nguyen and Huang [32] took a
similar approach with a flexible acceptable maximum aspect ratio in each
mentioned subset and some adjustments to the weights of sub-regions.

A third approach to this problem was developed by Vernier & Nigay [33]. Their
Modifiable treemaps algorithm allocates to each node of the tree a bounding
box with fixed aspect ratio, which can be modified by the user. It then
creates a new set of recursive steps between two recursive steps of Slice-and-
Dice [1, 2]. At each iteration, Modifiable generates several options from the
current set of sub-rectangles and picks the one with the minimum sum of
differences between the fixed aspect ratio and the aspect ratio of each
contained rectangle. The chosen option is then recursively partitioned. If the
fixed aspect ratios are set to 1 then the algorithm generates square-like
rectangles.

####  2.3.2 Ordering & Stability

While Slice-and-Dice [1, 2] preserves the original order of the leaves in the
tree structure, Cluster [22], Squarified [17], and Modifiable [33] do
not—violating the ordered criteria. Moreover, they violate the stable criteria
as they are not stable to changes in the input data.

Engdahl was able to preserve order with Split [34], while still offering
improved aspect ratios over Slice-and-Dice [1, 2]. Split takes an ordered list
of desired sub-rectangle areas and splits them into two lists, without
changing the order, such that the sum of areas is as close as possible across
lists. Split then divides the input rectangle with a vertical or horizontal
cut, depending on whether the width is larger than the height, then recurses.

Introducing the stability criteria, Shneiderman & Wattenberg’s Pivot [19] and
the Bederson et al.’s Strip [35] algorithms take compromise approaches that
still preserve ordering and good aspect ratios. Pivot selects one of the input
areas as the pivot element, places it as a square-like sub-rectangle to
partition the input rectangle $R$ into three areas, and then recursively lays
out rectangles from three lists $L_{1}$–$L_{3}$ into each of the areas.
$L_{1}$ includes all sub-rectangles whose index in the input order is less
than the index of the pivot. $L_{2}$ and $L_{3}$ are chosen such that the
indices of sub-rectangles in $L_{2}$ is less than the indices of sub-
rectangles in $L_{3}$ and the aspect ratio of the pivot is as close to 1 as
possible.

Strip adds rectangles one-by-one to strips, just like Squarified [17], but
fixes the orientation of strips throughout and omits the initial sorting step
to preserve order. Bederson et al. also introduce Quantum [35], which is
specially suited for cases where all leaf nodes should have the same size
(e.g., for photo browsers). For preserving order, Wood and Dykes took another
approach to modify Squarified by assigning to each node a two dimensional
location and proposed OrderedSquarified [24]. In a similar approach, Tu & Shen
[9] introduce Spiral treemaps that tries to preserve order and continuity
while minding the aspect ratios as the rectangles are being added. The
algorithm works just like the Strip algorithm except that starting from the
top left corner of $R$ the direction of the strip alternates in an east-south-
west-north manner. Other space-filling curves are also considered for
generating rectangular treemaps. Tak and Cockburn proposed Hilbert and Moore
treemaps [12] based on Hilbert and Moore fractal-like curves and showed that
they perform well with respect to stability measures. Fractal-like treemaps is
also used by D’Ambros et al. [36] to visualize the evolution of software
systems which can be used for over preservation. The main goal in these space-
filling curve-based treemaps is to preserve order and maximize stability and
_readability_ , where the latter is a measure to show the benefit of ordered
layouts and quantifies the simplicity of visually scanning a treemap layout by
counting e.g. the number of changes in direction a viewer’s eye must make when
scanning the rectangles in order [35]. In contrast to these, our spiral
algorithms do not aim to preserve order and instead try to construct a balance
between stability and aspect ratios. For this reason and the fact that they
generally perform poorly with respect to aspect ratio, as shown in [9, 12, 27,
23], we skip Spiral, Hilbert, and Moore in our computational comparisons.

Vernier et al. developed Greedy Insertion [37], aiming to balance aspect ratio
and stability criteria, although the results suggests that the algorithm
performs well on stability while scoring poorly on aspect ratio. It inserts
sub-rectangles into the given rectangle one-by-one greedily and in the given
order. Sondag et al. proposed Incremental [27] that tries to achieve stability
through local moves when an initial layout is given. For a thorough
comparative evaluation of dynamic treemap algorithms, we refer the reader to
Vernier et al. [23]. This study runs an extensive computational experiments
over more than 2000 data sets and compares 14 well-known treemap algorithms,
summarized in Fig. 8 – Fig. 11 in [23], and suggests that Squarified [17]
almost consistently outperforms all other well-known algorithms with respect
to aspect ratio (our main metric in this paper). This is also demonstrated by
the computational results over two large data sets summarized in Fig. 21 –
Fig. 26 in the paper [27]. The latter paper also shows that it performs
reasonably well with respect to stability on one of the large data sets and
performs weaker on the other one. For this reason we compare our results with
those of Squarified. For the same reason

####  2.3.3 Other Variants

There have also been a number of modifications to these algorithms to increase
aesthetics and readability.

Baker & Eick [38] adapted Slice-and-Dice [1, 2] by adding extra layers of
information for visualization of software subsystems and their associated
statistics. Likewise, van Wijk & van de Wetering [39] added a shaded surface
to each rectangle to highlight the hierarchical structure.

To have treemaps simulate standard chart types, Vliegen et al. [40] created
several treemap approaches and pixel transformations. As part of this, they
developed a Mixed algorithm that partitions higher-level nodes according to
Slice-and-Dice [1, 2] and places leaf nodes using Squarified [17]. They also
let users manually set the direction of cut in Slice-and-Dice at each
iteration, which would, e.g., let the user compare different categories of
data side-by-side. Another of their variations was to change Squarified so
that the vanishing point of small rectangles could be set to center instead of
a default corner. Likewise, Yang et al. [29] presented a variant of Slice-and-
Dice intended to better highlight the hierarchical structure in which the
layout resembles objects stacked in a cabinet.

To have treemaps better show spatial ordering, e.g., for a cartogram, Wood &
Dykes [24] modified Squarified [17] so that it both follows the given order of
the nodes and at the same time the Euclidean distance between the first placed
rectangle (the top left corner) and all other rectangles increases to the last
placed rectangle in a more smooth spatial transition. The algorithm modifies
the ordered list by associating a location dimension to each node and then
sorting the list again with regards to the ascending order of the spatial
distance between the child nodes (rectangles) and their parent nodes. It then
follows the recursive steps of Squarified but instead of selecting nodes from
a sorted list of areas, it selects the node closest to the current position in
the layout rectangle.

Duarte et al. [41] generalized the concept of order preservation to
neighborhood preservation. They developed the Nmap algorithm that uses a slice
and scale strategy to take a spatial data set in which each data point is
assigned a location $(x,y)\in\mathbb{R}^{2}$ and a weight $p\in\mathbb{R}$ and
present it as a treemap where the closeness of rectangles tends to follow the
closeness of the data points in $\mathbb{R}^{2}$, while maintaining the visual
quality.

Unlike most treemap algorithms which are constructive, the Incremental by
Sondag et al. [27] uses a local search. It can take an initial layout
generated by any of the constructive algorithms and then tries to improve
through a series of local moves like stretching and flipping, followed by the
readjustment of areas. As a result, it can potentially generate all possible
layouts—including _non-sliceable_ layouts, which are those that cannot be
recursively sliced into two parts having at least one rectangle as a center of
a windmill pattern. The algorithm generates layouts that score well both in
aspect ratio and stability. However, the output quality and computational time
greatly depends on the quality of the initial constructed layout as it takes
$\mathcal{O}(n^{2})$ to move from one layout to another—in addition to solving
several linear equality systems for readjusting areas in each iteration.

Non-rectangular treemaps have also been very popular. Balzer et al. [6, 7]
developed an algorithm for generating Voronoi treemaps, where the planar
figures representing the leaf nodes are the cells of a Voronoi diagram instead
of rectangles. The algorithm is based on computing a weighted centroidal
Voronoi tessellation (CVT) in which the weight of each sub-region is adjusted
so the area of each cell is within a threshold $\epsilon$ of the input
(desired) areas. They provide an variant using additively-weighted Voronoi
diagrams and power diagrams. Voronoi treemaps enable layouts within areas of
arbitrary shape, such as triangles and circles. However, computation of CVTs
is expensive and not suitable for dynamic updates in the input data.

Others tried to improve the computational efficiency and other aspects of
Voronoi treemaps [42, 20, 43, 44, 45]. Wang et al. [46] developed an
orthogonal Voronoi treemap in which borders of cells are axis-aligned.
Similarly, Wang et al. [47] proposed algorithms for generating Voronoi
treemaps based on Manhattan ($\ell_{1}$) and Chebychev ($\ell_{\infty}$)
distances. Liang et al. [4] extend Engdahl’s Split [34] and the polygonal
division idea of Nguyen & Huang [48] and use Divide & Conquer to create
polygonal, angular, and—relevant to this paper—rectangular treemaps that could
be laid out in almost any container shape.

The use of space-filling fractal-like curves may also produce non-rectangular
layouts such as Jigsaw treemaps [49] and Gosper treemaps [11]. Later,
Chaturvedi et al. [10] proposed two heuristic-based treemap layouts which did
not have any space-filling guarantees. Here, we only consider deterministic
data, but rectangular treemaps are also produced in presence of uncertainty
[50], in which case the layout structure could be overlapping. For a review on
different variants of treemaps see [15].

####  2.3.4 Performance Considerations

Despite the wide variety of rectangular and non-rectangular treemap
algorithms, less attention has been paid to performance guarantees.

Nagamochi & Abe [51] consider the problem of partitioning a rectangle $R$ into
$n$ rectangles with specified areas $A_{1},...,A_{n}$ with objective functions
such as the sum of the perimeters of the sub-rectangles (PERI-SUM), the
maximum perimeter of the sub-rectangles (PERI-MAX), and the maximum aspect
ratio of the sub-rectangles. They then present an $\mathcal{O}(n\log n)$
algorithm with a 1.25 approximation factor for PERI-SUM, a $2/\sqrt{3}$
approximation factor for PERI-MAX, and aspect ratio of at most
$\max\\{\mathop{\rm AR}(R),3,1+\max_{i=1,...,n-1}\frac{A_{i+1}}{A_{i}}\\}$.
The algorithm recursively partitions $R$ into two rectangles $R_{1}$ and
$R_{2}$ such that $\mathop{\rm Area}\nolimits(R_{1})\geq\frac{1}{3}\mathop{\rm
Area}\nolimits(R)$ and $\mathop{\rm
Area}\nolimits(R_{2})\geq\frac{1}{3}\mathop{\rm Area}\nolimits(R)$—except when
the maximum input area is greater than $\frac{1}{3}\mathop{\rm
Area}\nolimits(R)$, in which case $\mathop{\rm Area}\nolimits(R_{1})$ may not
meet this condition. If the input rectangle is a square, this improves the
1.75 approximation factor and the computational complexity of Beaumont et
al.’s algorithm for PERI-SUM [52], while extending the results for both PERI-
SUM and PERI-MAX to the case where the input rectangle is not necessarily a
square. Bui et al. [53] study the same problems under a strict rule that all
sub-rectangles must be constructed by two-stage guillotine cuts, first with
cuts parallel to the longer edge of $R$ and then with cuts perpendicular to
the first layer of cuts.

Onak & Sidiropoulos [5] present an algorithm using convex polygons as the sub-
regions, where the aspect ratio of each polygon, defined as $\mathop{\rm
AR}(P)=\frac{\mathop{\rm diam}(P)^{2}}{\mathop{\rm vol}(P)}$, is small. For a
tree with $n$ leaf nodes and depth $d$, this aspect ratio is of
$\mathcal{O}\left((d\cdot\log n)^{17}\right)$. This weak bound was later
improved to $\mathcal{O}(d+\log n)$ in [54, 55] and to $\mathcal{O}(d)$ in
[56]. They further prove that orthoconvex treemaps; where the sub-regions
representing leaf node are rectangles, L-, and S-shapes, and sub-regions
representing internal nodes are orthoconvex polygons; can be constructed with
constant aspect ratio.

For this paper, note the time complexities of Squarified [17]—and Divide &
Conquer [4]—$\mathcal{O}(n\log n)$.

##  3 Rectangular Treemapping as an Optimization Model

Treemapping is essentially a geometric optimization problem. There are many
closely-related geometric and space partitioning optimization problems that
include packing, covering, and tiling—generally focused on minimizing wasted
space or optimally allocating geographical resources. Related problems
include: cutting stock; knapsack; bin packing; guillotine; disk covering;
polygon covering; kissing number; strip packing; square packing; squaring the
square; squaring the plane; and, in 3D space, cubing the cube and tetrahedron
packing.

The treemapping problem—specifically with the goal of minimizing the maximum
aspect ratio of all sub-rectangles—was noted as NP-hard by Bruls et al. [17].
de Berg et al. later proved the problem is strongly NP-hard with a reduction
from the square packing problem [56]. The related treemapping problem of
minimizing the total perimeter of all sub-rectangles was proved by Beaumont et
al. [57] to be NP-hard, using a reduction from the problem of partitioning a
set of integers into two subsets of equal sum. Given this computational
complexity, several heuristics have been developed for generating treemaps
efficiently, as reviewed in the last section. In this paper, we will also
introduce several new heuristic algorithms.

Optimization approaches is understudied in the literature of the treemapping
problem. Zhao and Lu [58] modeled circular treemapping problem as an
optimization problem and developed a variational layout heuristic algorithm
based on power diagram to solve it. Carrizosa et al. [59] proposed a specific
type of treemap called space-filling box-connected map (SBM), with orthogonal
sub-regions that are made of grid cells and have to satisfy the so-called _box
connectivity constraints_ , and modeled it as a mixed integer nonlinear
program (MINLP) in which the objective is to minimize total dissimilarities
between sub-regions as measured by various distance functions defined
specifically for such sub-regions. They then solved it heuristically using a
Large neighborhood Search algorithm. Fried et al. [60] proposed a $p$-norm
(energy function) minimization model for the problem of assigning a set of
visual objects to a set spatial locations in form of a 2D grid. The pairwise
distances between objects are given and the goal is to minimize the
discrepancies between the given distances and the mapped distances measured by
the Euclidean distances between the grid cells. They then solve the problem
using a heuristic called _IsoMatch_.

Fügenschuh and Fügenschuh [61] modeled a metal sheet product design problem as
a 2D grid slicing problem as a binary integer program that in essence has some
similarities with the border length minimization in a grid-based orthogonal
treemapping problem. Fügenschuh et al. [62] considered the problem of
minimizing total border length in partitioning a rectangle to a set of sub-
rectanlged with given areas. They reiterated an MINLP model previously
presented and linearized as a mixed integer linear program in [63], modified
the approximation algorithm of [51], and used the solutions provided by that
as advanced starters and showed how this helps to speed-up the optimization
process. We noticed this work after finalizing this research and it seems to
be the closest in the literature to our model, which is more detailed,
explicit, and comprehensive. Our model incorporates several variants of
rectangular treemapping and considers a much bigger feasibility region. This
gives the user much more flexibility in generating treemaps with specifics
designs or characteristic requirements.

In order to provide a baseline for comparison, we propose an integer nonlinear
Optimization Model that minimizes the total perimeter of all sub-rectangles.
This is motivated by the fact that the perimeter of a rectangle is minimized
when it is a square. Note that this is a proxy for minimizing the average
aspect ratio and the optimal solution will consist of square-like rectangles.
One could consider minimizing the maximum perimeter or the maximum aspect
ratio as well. Nevertheless, the solution to these problems may not be the
same. To see this, consider an example with four rectangles and two solutions
with aspect ratios $\\{1,1,1,5\\}$ and $\\{1,2,3,4\\}$. The former is a better
solution concerning the average aspect ratio, while the latter is better
regarding the maximum aspect ratio.

To formally define our problem, suppose we are given a rectangle $R$ with
$\mathop{\rm width}(R)=w$ and $\mathop{\rm height}(R)=h$ aligned orthogonally
to the $x$ and $y$ axes with its lower-left corner at the origin. We are also
given numeric areas $A_{1},...,A_{n}$ s.t. $\sum_{i=1}^{n}A_{i}=\mathop{\rm
Area}\nolimits(R)$. We want to partition $R$ into $n$ non-overlapping
rectangular sub-regions $R_{1},...,R_{n}$ with areas $A_{1},...,A_{n}$ in a
way that the total perimeter of all rectangles (cut length) is minimized.

One of the advantages of our Optimization Model is that it can be easily
adjusted to incorporate specific constraints or other evaluation metrics. One
could change the objective function from total perimeter to maximum aspect
ratio or area weighted average aspect ratio or any other metric that could be
constructed as a function of dimensions or coordinates of the sub-regions.

Here, we consider a parametrized objective function to take advantage of this
flexibility. We consider an area-weighted total perimeter. We can switch
between the total perimeter and area-weighted version using a binary parameter
$\alpha\in\\{0,1\\}$. We also incorporate another degree of flexibility in our
objective function which may be very useful in practice. Often we may want to
compromise the aspect ratio slightly and in return gain rectangles that are
more horizontal, suitable for longer labels, or more aligned with each other,
making it easier to compare the areas. In order to do that, we define our
objective function as a weighted-average of total area-weighted perimeter and
the number of rectangles having greater width than height. Greater values for
the parameter $\beta\geq 0$ puts more weight on creating more horizontal
rectangles.

Similarly, we might be interested to modify the objective function to
incorporate our stability metric as well to make a trade-off between perimeter
(aspect ratio) and stability. We must point out that since all of sub-regions
in the generated treemaps are rectangles and thus convex, for any pair
$R,R^{\prime}$, the function $\mathop{\rm HD}(R,R^{\prime})$ is convex.
However, since $R^{\prime}$ is the corresponding sub-rectangle to $R$ in the
updated layout after perturbing areas (i.e., areas changing over time), the
exact formula of this metric and the way it should be added to the objective
function and then the solution analysis of that model is beyond the scope of
this paper. However, we can easily incorporate some design preferences such as
closeness of some sub-regions. Depending on the application, we may be
interested in having certain sub-rectangles close to each other in the final
treemap. Let, $\bm{v}^{i}$ denote the lower-left vertex of $R_{i}$. We can
measure the closeness between $R_{i}$ and $R_{j}$ by the Euclidean distance
between their lower-left corners, i.e., $\|\bm{v}^{i}-\bm{v}^{j}\|$.

We can also consider additional positioning and shape constraints. For
example, here we allow the user to opt, via parameter
$\delta_{i}\in\\{0,1\\},\;\forall i$, to fix the position of one sub-rectangle
to one of the corners of the input rectangle. We also allow the user to have
two particular sub-rectangles to be adjacent, i.e., sharing a corner, an edge
(two corners), or part of an edge, by adjusting parameters
$\eta_{ij},\theta_{ij}\in\\{0,1\\},\;\forall i,j$. Note that one could do this
for multiple rectangles too, however it may increase the risk of
infeasibility.

In the following we present an MINLP model for the considered problem. The
parameters for any rectangles $R_{i},R_{j}$ with $i,j\in\\{1,...,n\\}$ are:

$\displaystyle\alpha$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\text{area-weighted objective};\\\
0&\mbox{otherwise}.\end{array}\right.$ $\displaystyle\beta$ $\displaystyle:$ a
weight parameter for horizontality $\displaystyle\gamma_{ij}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\text{if }R_{i}\text{ is preferred
to be close to }R_{j};\\\ 0&\mbox{otherwise}.\end{array}\right.$
$\displaystyle\delta_{i}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\text{if }R_{i}\text{ has to be on
the lower left corner};\\\ 0&\mbox{otherwise}.\end{array}\right.$
$\displaystyle\text{We must have }\delta_{1}+\cdots+\delta_{n}\leq 1$
$\displaystyle\eta_{ij}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\text{if }R_{j}\text{ must be
adjacent to and to the right of }R_{i};\\\
0&\mbox{otherwise}.\end{array}\right.$ $\displaystyle\text{We must have
}\eta_{ij}+\eta_{ji}\leq 1.$ $\displaystyle\theta_{ij}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\text{if }R_{j}\text{ must be
adjacent to and above }R_{i};\\\ 0&\mbox{otherwise}.\end{array}\right.$
$\displaystyle\text{We must have }\theta_{ij}+\theta_{ji}\leq 1.$

The decision variables, for any rectangles $R_{i},R_{j}$ with
$i,j\in\\{1,...,n\\}$ are:

$\displaystyle w_{i}$ $\displaystyle:$ $\displaystyle\text{width of~{}}R_{i}$
$\displaystyle h_{i}$ $\displaystyle:$ $\displaystyle\text{height of~{}}R_{i}$
$\displaystyle\bm{v}^{i}$ $\displaystyle:$ $\displaystyle\text{ lower-left
corner of~{}}R_{i}\text{ with }\bm{v}^{i}=(v^{i}_{x},v^{i}_{y})$
$\displaystyle x_{ij}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\mbox{if
$v^{j}_{x}<v^{i}_{x}+w_{i}$};\\\ 0&\mbox{otherwise}.\end{array}\right.$
$\displaystyle y_{ij}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\mbox{if
$v^{j}_{y}<v^{i}_{y}+h_{i}$};\\\ 0&\mbox{otherwise}.\end{array}\right.$
$\displaystyle z_{i}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}1&\mbox{if $h_{i}\leq w_{i}$};\\\
0&\mbox{otherwise}.\end{array}\right.$

We can write our optimization problem as:

$\displaystyle\IEEEeqnarraymulticol{3}{l}{\mathop{\rm
minimize}\sum_{i=1}^{n}\left((1-\alpha+\alpha A_{i})((w_{i}+h_{i})-\beta
z_{i})\right)}$
$\displaystyle\IEEEeqnarraymulticol{3}{l}{\qquad\qquad\qquad+\sum_{i,j=1}^{n}\gamma_{ij}\|\bm{v}^{i}-\bm{v}^{j}\|\qquad\qquad\qquad\textnormal{s.t.}}$
$\displaystyle\log A_{i}-\log w_{i}-\log h_{i}$ $\displaystyle\leq$
$\displaystyle 0,\qquad\qquad\qquad\forall i$ (9) $\displaystyle
v^{i}_{x}+w_{i}$ $\displaystyle\leq$ $\displaystyle
w,\qquad\qquad\qquad\forall i$ (10) $\displaystyle v^{i}_{y}+h_{i}$
$\displaystyle\leq$ $\displaystyle h,\qquad\qquad\qquad\forall i$ (11)
$\displaystyle v^{i}_{x}+v^{i}_{y}$ $\displaystyle\leq$
$\displaystyle(w+h)(1-\delta_{i}),\qquad\forall i$ (12) $\displaystyle
v^{i}_{x}-v^{j}_{x}+w_{i}$ $\displaystyle\leq$ $\displaystyle
wx_{ij},\qquad\qquad\forall i,j$ (13) $\displaystyle
v^{i}_{x}-v^{j}_{x}+w_{i}$ $\displaystyle\geq$
$\displaystyle(\epsilon-w(1-x_{ij}))(1-\eta_{ij}),\,\forall i,j\;$ (14)
$\displaystyle x_{ij}$ $\displaystyle\leq$ $\displaystyle
1-\eta{ij}\qquad\qquad\forall i,j$ (15) $\displaystyle
v^{i}_{y}-v^{j}_{y}+h_{i}$ $\displaystyle\leq$ $\displaystyle
hy_{ij},\qquad\qquad\forall i,j$ (16) $\displaystyle
v^{i}_{y}-v^{j}_{y}+h_{i}$ $\displaystyle\geq$
$\displaystyle(\epsilon-h(1-y_{ij}))(1-\theta_{ij}),\>\forall i,j$ (17)
$\displaystyle y_{ij}$ $\displaystyle\leq$ $\displaystyle
1-\theta_{ij}\qquad\qquad\forall i,j$ (18) $\displaystyle
x_{ij}+x_{ji}+y_{ij}+y_{ji}$ $\displaystyle\leq$ $\displaystyle 3,\quad\forall
i,j$ (19) $\displaystyle w_{i}$ $\displaystyle\geq$ $\displaystyle
h_{i}-h(1-z_{i}),\qquad\forall i$ (20) $\displaystyle h_{i}$
$\displaystyle\geq$ $\displaystyle w_{i}-wz_{i},\qquad\qquad\forall i$ (21)
$\displaystyle v^{i}_{x},\;v^{i}_{y},\;w_{i},\;h_{i}$ $\displaystyle\geq$
$\displaystyle 0,\qquad\qquad\forall i$ $\displaystyle x_{ij},\;y_{ij}$
$\displaystyle\in$ $\displaystyle\\{0,1\\},\qquad\forall i,j$ $\displaystyle
z_{i}$ $\displaystyle\in$ $\displaystyle\\{0,1\\},\qquad\forall i$

where $\epsilon>0$ is a very small real number. Constraint (9), written in its
convex form, is to ensure that each rectangle $R_{i}$ with width $w_{i}$ and
height $h_{i}$ will have its associated area as $A_{i}=w_{i}\times h_{i}$.
Note that this constraint will be active at optimality. Constraints (10) and
(11) guarantee that the ending point of any rectangle on both axes should not
violate the width and height of $R$. Constraint (12) allows the solver to fix
one rectangle’s position to have its lower left corner on the origin.
Constraints (13)–(19) are added to avoid overlapping among rectangles as well
as to enforce adjacencies if required. Finally, constraints (20) and (21)
determine weather a sub-rectangle is horizontal. Fig. 3 shows an
implementation of this new model over random examples in layout boxes with
aspect ratios 1,2, and 3, and compares the sensitivity of the results to one
of the parameters, i.e., different values of $\beta$.

$\beta$=0 |  $\beta$=0.05 |  $\beta$=0.10
---|---|---
|  |
|  |
|  |

(a) Perimeter = 10.3906

(b) Perimeter = 10.4856

(c) Perimeter = 10.6854

(d) Perimeter = 11.2766

(e) Perimeter = 11.2766

(f) Perimeter = 11.4870

(g) Perimeter = 10.3842

(h) Perimeter = 10.3842

(i) Perimeter = 11.7842

Figure 3: An illustration of treemaps generated by our Optimization Model for
three different wight factors $\beta=0,\;0.05,\;0.1$, while all other
parameters are set to zero. Larger values of $\beta$ generate more horizontal
rectangles to fit longer labels. Note the _non-sliceable_ layouts in cases:
3(a), 3(b), and 3(i). For each treemap, the total perimeter of the component
subrectangles is shown with the best (shortest) and second-best values shown
using color.

A major advantage of this Optimization Model approach is that it focuses on
the optimal placement of each sub-region as opposed to dividing the region by
guillotine cuts. Therefore, it explores all possible layouts including the
_non-sliceable_ layouts (see Figs. 5(a) and 5(m)). This problem is NP-hard, as
mentioned above and proved in [57].

In the rest of this paper, we provide several suboptimal but efficient
algorithms for this optimization problem. In Section 4 we will present our
subdivision-based algorithms and in Section 5 we will develop our packing-
based algorithms. In these algorithms, similar to our Optimization Model,
minimizing the total perimeter (and thus the relevant aspect ratio measures)
is our main goal and stability is more of a secondary metric for comparison
and is not directly targeted. However, by construction, stability has a higher
weight in our spiral algorithms. We compare these to Optimization Model which
gives the absolute best treemaps concerning aspect ratios (when the input
region is given), Squarified [17] which has one of the best performance in the
literature with respect to creating square-like rectangles, and Divide &
Conquer [4] due to its similar approach and that it also performs well and can
lay out rectangles in any container shape.

##  4 Subdivision Algorithms

###  4.1 A Modified Divide and Conquer Algorithm

Given the structure of the problem, which is based on a tree, it is natural to
take a divide and conquer approach. Our divide and conquer algorithm is in the
same spirit of Liang et al.’s Divide & Conquer [4] algorithm, which appears to
be an extension of Engdahl’s Split [34] and the best already existing divide
and conquer approach to treemapping. Divide & Conquer tries to divide the
input areas into two lists of equal weights in each iteration and recursively
continues that until each sublist has only one area.

However, this is sensitive to the input parameters and works well only when
there is no extreme area. E.g., take a $8\times 4$ rectangle to be partitioned
into 18 sub-rectangles with areas $\\{15,1,1,1,...,1\\}$. The algorithm sets
$S_{1}=\\{R_{1},R_{2}\\}$ and $S_{2}=\\{R_{3},...,R_{18}\\}$ with
$\sum_{i:R_{i}\in S_{1}}A_{i}=\sum_{i:R_{i}\in S_{2}}A_{i}=16$. This will
generate a very thin rectangle $R_{2}$. In the rectangular version of the
algorithm we would have $\mathop{\rm Perim}(R_{2})=2\times(4+1/4)=8.5$ and
$\mathop{\rm AR}(R_{2})=16$. It is clear that setting $S_{1}=\\{R_{1}\\}$ and
$S_{2}=\\{R_{2},R_{3},...,R_{18}\\}$ could generate a much better result with
the maximum aspect ratio very close to 1.

An alternative approach is to divide the list of areas in half according to
the indices, i.e., $S_{1}=\\{R_{1},...,R_{8}\\}$ and
$S_{2}=\\{R_{9},...,R_{18}\\}$ for our example above, and then recur on each
sub-list. But this suffers from the same problem as Divide & Conquer [4] with
extreme areas. However, we propose a remedy.

In our new Modified D&C algorithm we first divide the input set of areas into
two equally weighted lists $S_{1}=\\{A_{1},...,A_{k_{1}},A_{k}\\}$ and
$S_{2}=\\{A_{k+1},A_{k+2},...,A_{n}\\}$. We then check an additional condition
that could change the list that $A_{k}$ or $A_{k+1}$ belong to. For some real
$c>0$, if $|A_{\max\\{1,k-1\\}}-A_{k}|>c*|A_{k}-A_{\min\\{k+1,n\\}}|$, we pick
the best out of adding $A_{k}$ to $S_{2}$ or $A_{k+1}$ to $S_{1}$ by running
both. Otherwise, we make no change and continue the divide and conquer as
usual. Parameter $c$ can be adjusted by the user and gives additional
flexibility to the algorithm (in our experiments we use $c=2$). Intuitively,
this algorithm tries to avoid generating long and skinny rectangles at the
division points. So, a significant improvement in the maximum aspect ratio
metric is expected.

The pseudocode for Modified D&C, for the case where cuts are either vertical
or horizontal (depending on the width & height of the remaining segment), is
shown in algorithm 1. As with Divide & Conquer, it can be easily modified and
generalized to handle polygonal and angular cuts and to have no restriction on
input layout container shape. This Modified D&C algorithm remedies the issue
in Divide & Conquer in the same computational time of $\mathcal{O}(n\log n)$.

1

Input: Rectangle $R$, a list of $n$ areas $L=\\{A_{1},A_{2},...,A_{n}\\}$ with
$\sum_{i=1}^{n}A_{i}=\mathop{\rm Area}\nolimits(R)$, and a real constant $c$.

Output: Partition $R_{1},R_{2},...,R_{n}$ with areas $A_{1},A_{2},...,A_{n}$.

/* *********************************************** */

2 Function  _main(_R,L_)_

3 Let $w$ denote the width of $R$ and $h$ be the height;

4 if  _$\left|L\right|=1$_ then

5 return _$(w+h,R)$_ ;

6

7 else

8 Sort $L$ in a non-increasing order and reindex the sorted areas as
$A_{1},A_{2},...,A_{n}$;

9 return _${\sf Partition}(R,L,1,n,c)$_ ;

10

11 end if

12

13

1 Procedure  _Partition(_$Q,L,\mbox{start, stop},c$_)_

2 Let $w$ denote the width of $Q$ and $h$ be the height;

3 Set $S_{1}=0$ and $S_{2}=\sum_{i=start}^{stop}{A_{i}}$;

4 for  _$k=\textrm{start : stop}-1$_ do

5 Set $S_{1}=S_{1}+A_{k}$;

6 Set $S_{2}=S_{2}-A_{k}$;

7 if  _$|S_{1}-S_{2}| <|(S_{1}+A_{k+1})-(S_{2}-A_{k+1})|$_ then

8 break;

9

10 end if

11

12 end for

13 if  _$A_{\max(start,k-1)}-A_{k} >c*(A_{k}-A_{\min(k+1,stop)})$_ then

14 Set $S_{1}^{\prime}=S_{1}-A_{k}$ and $S_{2}^{\prime}=S_{2}+A_{k}$;

15 Set $S_{1}^{\prime\prime}=S_{1}+A_{k+1}$ and
$S_{2}^{\prime\prime}=S_{2}-A_{k+1}$;

/* Set $L_{1}^{\prime}=\\{A_{start},...,A_{k-1}\\}$ and
$L_{2}^{\prime}=\\{A_{k},...,A_{stop}\\}$; */

/* Set $L_{1}^{\prime\prime}=\\{A_{start},...,A_{k+1}\\}$ and
$L_{2}^{\prime\prime}=\\{A_{k+2},...,A_{stop}\\}$; */

16 if  _$w >h$_ then

17 Divide $Q$ vertically into two pieces $Q_{1}^{\prime}$ with
$w_{1}^{\prime}=S_{1}^{\prime}/h$ and $h_{1}^{\prime}=h$ on the left and
$Q_{2}^{\prime}$ with $w_{2}^{\prime}=w-S_{2}^{\prime}/h$ and
$h_{2}^{\prime}=h$ on the right;

18 Divide $Q$ vertically into two pieces $Q_{1}^{\prime\prime}$ with
$w_{1}^{\prime\prime}=S_{1}^{\prime\prime}/h$ and $h_{1}^{\prime\prime}=h$ on
the left and $Q_{2}^{\prime\prime}$ with
$w_{2}^{\prime\prime}=w-S_{2}^{\prime\prime}/h$ and $h_{2}^{\prime\prime}=h$
on the right;

19

20 else

21 Divide $Q$ horizontally into two pieces $Q_{1}^{\prime}$ with
$w_{1}^{\prime}=w$ and $h_{1}=S_{1}^{\prime}/w$ on top and $Q_{2}^{\prime}$
with $w_{2}^{\prime}=w$ and $h_{2}=h-S_{2}^{\prime}/w$ in bottom;

22 Divide $Q$ horizontally into two pieces $Q_{1}^{\prime\prime}$ with
$w_{1}^{\prime\prime}=w$ and $h_{1}^{\prime\prime}=S_{1}^{\prime\prime}/w$ on
top and $Q_{2}^{\prime\prime}$ with $w_{2}^{\prime\prime}=w$ and
$h_{2}^{\prime\prime}=h-S_{2}^{\prime\prime}/w$ in bottom;

23

24 end if

_25_ _ _return _the best out of_

_26_ __
$\textnormal{{Partition}}(Q_{1}^{\prime},L,start,k-1,c)\cup\textnormal{{Partition}}(Q_{2}^{\prime},L,k,stop,c)$

_27_ __ and

28  __
$\textnormal{{Partition}}(Q_{1}^{\prime\prime},L,start,k+1,c)\cup\textnormal{{Partition}}(Q_{2}^{\prime\prime},L,k+2,stop,c)$;

29

30 else

/* Set $L_{1}=\\{A_{start},...,A_{k}\\}$ and
$L_{2}=\\{A_{k+1},...,A_{stop}\\}$; */

31 if  _$w >h$_ then

32 Divide $Q$ vertically into two pieces $Q_{1}$ with $w_{1}=S_{1}/h$ and
$h_{1}=h$ on the left and $Q_{2}$ with $w_{2}=w-S_{2}/h$ and $h_{2}=h$ on the
right;

33

34 else

35 Divide $Q$ horizontally into two pieces $Q_{1}$ with $w_{1}=w$ and
$h_{1}=S_{1}/w$ on top and $Q_{2}$ with $w_{2}=w$ and $h_{2}=h-S_{2}/w$ in
bottom;

36

37 end if

38 return
_$\textnormal{{Partition}}(Q_{1},L,start,k,c)\cup\textnormal{{Partition}}(Q_{2},L,k+1,stop,c)$_
;

39

40 end if

41

42

Algorithm 1 Modified D&C $(R,L,c)$ Generates a rectangular treemap with the
given areas and bounding rectangle according to a modified divide and conquer
approach.

###  4.2 A Dynamic Programming Approach

We can improve the quality even further. Here, we present a new Dynamic
Programming algorithm that dynamically picks the best dividing point to
minimize the objective function. First, we sort the list of areas in non-
ascending order. Then, in each step, we divide the areas into two sub-lists.
With these, we dissect $R$ into two sections by a guillotine cut so that each
has an area equal to the total area of its associated list. We find the
dividing point in the list of areas in each iteration using the recursive
equation:

$\displaystyle P_{(i)}$ $\displaystyle:$ $\displaystyle\text{The perimeter of
sub-rectangle~{}}R_{i}$ $\displaystyle P_{(i,j)}$ $\displaystyle:$
$\displaystyle\text{The total perimeter of sub-rectangles~{}}R_{i\ldots j}$
$\displaystyle P_{(1,n)}$ $\displaystyle=$ $\displaystyle\min_{1\leq k\leq
n}\\{P_{(1,k)}+P_{(k+1,n)}\\}$ $\displaystyle P_{(i,j)}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}P_{(i)}&\mbox{if $i=j$}\\\ {}\\\
\min_{i\leq k<j}\\{P_{(i,k)}+P_{(k+1,j)}\\}&\mbox{if $i<j$}\end{array}\right.$
(25)

This approach of course leads to a high quality solution due to considering a
much larger feasible space, but also leads to an exponential running time of
$\mathcal{O}(3^{n})$. The reason is unlike the partitioning of a discrete set
of numbers areas, each subset of areas $\\{A_{i},...,A_{j}\\}$ could represent
several different subproblems depending on the the location of those sub-
rectangles and the sequence of vertical and horizontal cuts that lead us
there. This makes it impossible to cache the best solutions for each
subproblem to be used in future calls which leads to solving each subproblem
from scratch.

1

Input: Rectangle $R$ and a list of $n$ areas $L=\\{A_{1},A_{2},...,A_{n}\\}$
with $\sum_{i=1}^{n}A_{i}=\mathop{\rm Area}\nolimits(R)$.

Output: Partition $R_{1},R_{2},...,R_{n}$ with areas $A_{1},A_{2},...,A_{n}$.

/* *********************************************** */

2 Function  _main(_R,L_)_

3 Let $w$ denote the width of $R$ and $h$ be the height;

4 if  _$n=1$_ then

5 return _$(w+h,R)$_ ;

6

7 else

8 Sort $L$ in a non-increasing order and reindex the sorted areas as
$A_{1},A_{2},...,A_{n}$;

/* pBest is a structured array to store best perimeter and best partition for
a block $A_{i},...,A_{j}$ in a rectangle with width $w$ and height $h$ and its
lower left corner on the origin. */

9 Let $\mbox{pBest}=\\{\;\\}$;

10 return _${\sf Partition}(R,L,1,n)$_ ;

11

12 end if

13

14

1 Procedure  _Partition(_$Q,L,\mbox{start, stop}$_)_

2 Let $w$ denote the width of $Q$ and $h$ be the height;

3 Let $\bm{q}=(q_{x},q_{y})$ be the lower left corner of $Q$ and
$\bm{q_{0}}=(0,0)$;

/* pBest stores the best partition of a box $B$ with $\bm{q}_{B}=\bm{q_{0}}$
and area $\sum_{i=\mbox{\tiny start}}^{\mbox{\tiny stop}}A_{i}$ into sub-
rectangles $R_{\mbox{start}},...,R_{\mbox{stop}}$ */

4 if  _the 4-tuple $\mbox{(start, stop,}w,h)$ exists in pBest.ID_ then

5 Let $k$ be the index in pBest.ID that stores $\mbox{(start, stop,}w,h)$;

6 return _$(\mbox{pBest.Perim(k)},(\mbox{pBest.Par(k)}+\vec{\bm{q}}))$_ ;

7

8 else

9 Set $\mbox{bestPrm}=$ An arbitrary large number;

10 if  _start = stop_ then

11 Set $\mbox{bestPrm}=w+h$;

12 Set $\mbox{bestPar}=Q$;

13

14 else

15 for  _$k=\textrm{start : stop}-1$_ do

16 Set $S=\sum_{i=\mbox{\tiny start}}^{k}{A_{i}}$;

17 Divide $Q$ vertically into two pieces $Q_{1}$ with $w_{1}=S/h$ and
$h_{1}=h$ on the left and $Q_{2}$ with $w_{2}=w-S/h$ and $h_{2}=h$ on the
right;

18 Divide $Q$ horizontally into two pieces $Q_{3}$ with $w_{3}=w$ and
$h_{3}=S/w$ on top and $Q_{4}$ with $w_{4}=w$ and $h_{4}=h-S/w$ in bottom;

19 Let $[\mbox{Prm}_{1},\mbox{Par}_{1}]={\sf
Partition}(Q_{1},L,\mbox{start},k)$;

20 Let $[\mbox{Prm}_{2},\mbox{Par}_{2}]={\sf
Partition}(Q_{2},L,k+1,\mbox{stop})$;

21 Let $[\mbox{Prm}_{3},\mbox{Par}_{3}]={\sf
Partition}(Q_{3},L,\mbox{start},k)$;

22 Let $[\mbox{Prm}_{4},\mbox{Par}_{4}]={\sf
Partition}(Q_{4},L,k+1,\mbox{stop})$;

23 if  _$(\mbox{Prm}_{1}+\mbox{Prm}_{2}) <(\mbox{Prm}_{3}+\mbox{Prm}_{4})$_
then

24 Set $\mbox{tmpPrm}=\mbox{Prm}_{1}+\mbox{Prm}_{2}$;

25 Set $\mbox{tmpPar}=\mbox{Par}_{1}\cup\mbox{Par}_{2}$;

26

27 else

28 Set $\mbox{tmpPrm}=\mbox{Prm}_{3}+\mbox{Prm}_{4}$;

29 Set $\mbox{tmpPar}=\mbox{Par}_{3}\cup\mbox{Par}_{4}$;

30

31 end if

32 if  _$\mbox{tmpPrm} <\mbox{bestPrm}$_ then

33 Set $\mbox{bestPrm}=\mbox{tmpPrm}$;

34 Set $\mbox{bestPar}=\mbox{tmpPar}$;

35

36 end if

37

38 end for

39

40 end if

41 Set pBest.ID = [pBest.ID, ($\mbox{start,stop,}w,h$)];

42 Set pBest.Perim = [pBest.Perim, bestPrm];

43 Set pBest.Par = [ pBest.Par, ($bestPar-\vec{\bm{q}}$)];

44

45 end if

46 return _$(\mbox{bestPrm},\mbox{bestPar})$_ ;

47

48

Algorithm 2 Dynamic Programming $(R,L)$ Generates a rectangular treemap with
the given areas and bounding rectangle according to a divide and conquer
approach with optimized division process.

However, we can remedy this with some modifications. By adding the width
$w_{b}$ and height $h_{b}$ of the box $B$ which we want to partition it to a
block of areas $A_{i},...,A_{j}$ to the sequence $\\{i,...,j\\}$ as the
identifier of a subproblem we can save solved subproblems and potentially
reuse them in future calls. Regardless of the location of $B$ inside the input
rectangle $R$, (25) will always find the same value, as long as the shape
(width and height) of $B$ does not change. Hence, we define a subproblem by
$(i,j,w_{b},h_{b})$. Using this identifier, we will save the best solution for
each subproblem to avoid solving these subproblems from scratch each time they
occur. Besides the perimeter we also need to save the partitioning structure.
This creates a challenge because rectangles of dimension $w_{b}\times h_{b}$
can have their lower left corner almost anywhere inside $R$. To do this, we
assume the left corner of $B$ in the saved subproblem to be the origin and
then we define $T:\mathcal{P}+t\vec{\bm{v}}$ with $t\in\mathbb{R}$ as a
translation operator on the set $\mathcal{P}$ that in the direction
$\vec{\bm{v}}$, in which the shift is applied to every point
$\bm{x}\in\mathcal{P}$. This operator handles the necessary shifts between the
boxes. This modification improves the running time down to
$\mathcal{O}(n^{3})$.

Algorithm 2 shows the detailed steps of this approach. The direction of the
cuts, similar to Divide & Conquer [4], could be rectangular, angular, or
polygonal. Here we implement the rectangular approach with vertical and
horizontal cuts, but replacing the type of cut is an easy generalization. Our
algorithm can also be easily modified to handle non-rectangular layout
containers to partition them into other polygonal sub-regions. Example
treemaps made with Dynamic Programming are shown in Figs. 4(a) and 4(b) for
stock market sectors and Figs. 4(c) and 4(d) for state populations. There, we
use both rectangular and hexagonal layout containers.

(a)

(b)

(c)

(d)

Figure 4: Treemaps generated using our Dynamic Programming approach laid out
in a rectangle or hexagon. 4(a) and 4(b) show the market capitalization of
each sector of the U.S. Stock Market after closing on 2020-12-18. 4(c) and
4(d) display ratios of population of 12 states in the Midwest based on 2010
U.S. Census data.

Besides being able to handle cases with extreme areas, our computational
results in Section 6 show that our Dynamic Programming algorithm performs
significantly better than Divide & Conquer [4] with respect to aspect ratio
and stability metrics.

###  4.3 Comparison of Recursive Subdivision Approaches

We compare the results of the divide and conquer algorithms and dynamic
programming algorithm with Optimization Model using several examples.

Consider a tree with 7 leaves with weights $(w_{1},...,w_{7})=$ (0.1277,
0.0837, 0.0922, 0.2235, 0.2845, 0.0994, 0.0890), that add up to 1. Assume,
without loss of generality, that we want to visualize it in a treemap with a
unit square as the layout container in a way to minimize the total perimeter
of the rectangles. Fig. 5(a)–Fig. 5(d) show the results using Optimization
Model, our dynamic programming and divide and conquer algorithms, and Divide &
Conquer [4]. Optimization Model results in the lowest total perimeter,
followed by Dynamic Programming.

Fig. 5(e)–Fig. 5(g) compare the same approaches for an extreme random example
$(w_{1},...,w_{7})=$ (0.0795, 0.0709, 0.1074, 0.1121, 0.3980, 0.1023, 0.1298),
where one weight (area) is much larger. In this extreme case, Dynamic
Programming performs very well and in fact found the optimal solution.

We repeat the comparison for the treemap of market capitalization of different
sectors in the U.S. Stock Market (Fig. 5(i)–Fig. 5(k)) and ratios of
population of the states in the U.S. Midwest (Fig. 5(m)–Fig. 5(o)). In both
cases, Optimization Model performs best followed by Dynamic Programming.

We have only been comparing the results by the total perimeter metric—the
objective function of Optimization Model. It should be mentioned that when the
optimal solution was sliceable Dynamic Programming was able to find it (Fig.
5(f)). We can generally say that when optimal solution is sliceable Dynamic
Programming can either find it or get very close to it. However, just like
most other treemap algorithms it does not explore non-sliceable layouts.
Divide & Conquer and Modified D&C performed more or less similar to each other
on these examples. Section 6 details more comprehensive comparisons that show
both Dynamic Programming and Modified D&C beat Divide & Conquer of [4].

| Optimization Model | Dynamic Programming | Modified D&C |  Divide & Conquer [4]
---|---|---|---|---
| Random
---
$L=\\{$
$0.1277,$
$0.0837,$
$0.0922,$
$0.2235,$
$0.2845,$
$0.0994,$
$0.0890$
$\\}$
|  |  |
| Random
---
Extreme
$L=\\{$
$0.0795,$
$0.0709,$
$0.1074,$
$0.1121,$
$0.3980,$
$0.1023,$
$0.1298$
$\\}$
|  |  |
| Stock
---
Market
|  |  |
| State
---
Pop.
|  |  |

(a) Perimeter = 10.3906

(b) Perimeter = 10.4649

(c) Perimeter = 10.4649

(d) Perimeter = 10.6092

(e) Perimeter = 10.1965

(f) Perimeter = 10.1965

(g) Perimeter = 10.1965

(h) Perimeter = 10.5111

(i) Perimeter = 12.6130

(j) Perimeter = 12.7082

(k) Perimeter = 12.9822

(l) Perimeter = 12.9051

(m) Perimeter = 12.8988

(n) Perimeter = 13.0456

(o) Perimeter = 13.2752

(p) Perimeter = 13.2155

Figure 5:  These visualizations show the effect of applying four treemap
layout algorithms to four weighted, single level trees. The treemaps are
generated and laid out in a unit box using either our Optimization Model, our
dynamic divide and conquer algorithm (Dynamic Programming), our modified
divide and conquer algorithm (Modified D&C), or the divide and conquer
approach of Liang et al. [4] (Divide & Conquer). Two of the trees have seven
leaves with random weights (areas, given by $L=\\{\ldots\\}$), with the second
(Extreme) example containing a weight much larger than the others. The third
tree shows the market capitalization of different sectors in the U.S. Stock
Market after closing on 2020-12-18. The final tree shows ratios of state
population in the U.S. Midwest from the 2010 U.S. Census. For each treemap,
the total perimeter of the component subrectangles is shown with the best
(shortest) and second-best values shown using color. Note that Optimization
Model results in the shortest perimeter. Our Dynamic Programming performs the
best among the algorithms. Our Modified D&C gives better results than Divide &
Conquer on two instances including the extreme example (for which it is
designed), and performs weaker on the other two instances. The extreme example
shows the largest gap between the two algorithms as expected. It is clear that
the gap on maximum aspect ratio metric is even larger. Moreover, it produces
_non-sliceable_ layouts in three cases: 5(a), 5(i), and 5(m).

##  5 Constructive Algorithms for Spiral Treemaps

Most of the existing algorithms, including the algorithms we introduced in the
previous section, generate treemaps that lack an overall pattern. Such
patterns could make treemaps more appealing visually, make it easier to
compare the size of different sub-regions, and facilitate spotting specific
sub-regions (increasing the readability as described in Bederson et al. [35]).

In contrast, spiral treemaps place the sub-regions in a way that the overall
layout resembles a spiral centered inside the container. As opposed to
treemaps created by guillotine cuts or by sequential placement of rectangles
in horizontal or vertical directions, spiral treemaps have not been adequately
studied [9]. Here we present three new algorithms for generating spiral
treemaps with rectangular sub-regions.

An experiment conducted by Kong et al. [3] suggests that rectangles with large
aspect ratios $\geq$ 9/2 reduce the accuracy of area comparison tasks,
particularly when the rectangles have different orientations. They also show
that the accuracy of the perception is equally poor when comparing squares.
What actually seems to help is having a distribution of reasonable non-square
aspect ratios. Their results particularly show that optimizing towards a 3/2
aspect ratio performs better than Squarified. Lu et al. [64] present an
algorithm that, instead of targeting squares like Squarified, tries to reach a
layout with rectangles having aspect ratios as close as possible to the golden
ratio $\phi=\frac{1+\sqrt{5}}{2}\simeq 1.618$—so-called golden rectangles.
This is also close to the 3/2 ratio conjectured by Kong et al..

Golden ratios, golden rectangles, and golden spirals have been discovered in
nature, human body, and galaxies, and have been used frequently in
architecture (e.g., _Great Mosque of Kairouan_ in Tunisia [65], and _Naqsh-e
Jahan Square_ in Iran [66, 67])111The popular golden ratio example of the
Parthenon temple in ancient Greece is disputed and seems to be without
foundation [68]., in art (e.g., the painting “ _The Sacrament of the Last
Supper_ ” by Salvador Dali [69]), in finance (e.g., the use of _Fibonacci
retracement levels_ in prediction of stock price changes [70]), and in
optimization (e.g., _golden section search_ [71]). Here, we follow the same
intuition and generate treemaps that mimic the _golden spiral_ or its
approximation the _Fibonacci spiral_.

###  5.1 Symmetric Spiral Treemap Algorithm

Our new Symmetric Spiral layout first sorts the input areas in non-descending
order. Then, starting with the first two sub-rectangles ($R_{1}$ and $R_{2}$)
in the sorted list, we juxtapose the sub-rectangles ($R_{2}$ to the left of
$R_{1}$) with the same height so that their union forms a larger rectangle
with aspect ratio of 2. The choice of aspect ratio of these two initial
placements is driven by the way the _Fibonacci spiral_ is constructed. We
denote this aspect ratio with $\rho_{s}$ and treat it as a configurable
parameter. The direction then changes and the next rectangle is placed on top
of the union of the current rectangles, forming a larger rectangle. Again,
direction changes and the next rectangle is placed to the right of the union
of already-placed rectangles. This procedure is repeated until all rectangles
are placed. A new rectangle is added in each step and its union with
previously-placed rectangles forms a larger rectangle. Direction turns
clockwise between left, top, right, and bottom.

Pseudocode for Symmetric Spiral is shown in algorithm 3, and its computational
complexity is $\mathcal{O}(n\log n)$ due to the sorting step; the rest of the
algorithm runs in $\mathcal{O}(n)$. In algorithm 3 we follow a clockwise-
outward-growing rotation for forming the spiral structure. Unfortunately,
Symmetric Spiral is wont to create skinny rectangles as the spiral gets closer
to the outermost layer. This is due to placing each new sub-rectangle on the
longer side of the union of currently-placed sub-rectangles. Therefore, the
aspect ratios of the sub-rectangles could get worse as the spiral is growing.
However, our goal in this algorithm is really not to produce high quality
treemaps with respect to aspect ratio metrics. Symmetric Spiral serves a
purpose like Slice-and-Dice as our basis for the next two and future spiral
treemaps. It also generally produces more _readable_ and aesthetically
appealing visualization by maximizing _symmetry_ and _fractal-like patterns_
in the treemaps. One could define evaluation metrics for these properties,
e.g., readability measure introduced in [35] and the Fractal Value as defined
in Eq. (1) in [36], and evaluate the quality of this algorithm that way, which
is out of the scope of this paper.

Input: A list of $n$ areas $L=\\{A_{1},A_{2},...,A_{n}\\}$.

Output: A rectangle $R$ partitioned into $n$ sub-rectangles
$R_{1},R_{2},...,R_{n}$ with areas $A_{1},A_{2},...,A_{n}$ such that
$\mathop{\rm Area}\nolimits(R)=\sum_{i=1}^{n}A_{i}$.

/* *********************************************** */

1 if  _$n=1$_ then

2 return _$R_{1}$_ ;

3else

4 Sort the list of areas in ascending order and reindex the sorted areas as
$A_{1},A_{2},...,A_{n}$;

/* Ensuring $R_{1}$ and $R_{2}$ together form a bigger rectangle with aspect
ratio $\rho_{s}=2$. */

5 Set $h_{1}=h_{2}=\sqrt{(A_{1}+A_{2})/2}$, $w_{1}=A_{1}/h_{1}$, and
$w_{2}=A_{2}/h_{2}$;

6 Place $R_{2}$ on the left of $R_{1}$;

7 Let $Q_{2}=\Box(R_{1}\cup R_{2})$;

8 if  _$n=2$_ then

_9_ _ _return _$Q_{2},R_{1},R_{2}$ ;_

10

11 else

12 Set $\mbox{direction}=$ “top”;

13 for  _$i\in\\{3,...,n\\}$_ do

14 if  _$\mbox{direction}=$ “top”_ then

15 Set width $w_{i}=\mathop{\rm width}(Q_{i-1})$, height $h_{i}=A(i)/w_{i}$,
and place rectangle $R_{i}$ exactly on top of $Q_{i-1}$;

16 Set $\mbox{direction}=$ “right”;

17 else if  _$direction=$ “right”_ then

18 Set height $h_{i}=\mathop{\rm height}(Q_{i-1})$, width $w_{i}=A(i)/h_{i}$,
and place rectangle $R_{i}$ exactly on the right side of $Q_{i-1}$;

19 Set $\mbox{direction}=$ “bottom”;

20 else if  _$direction=$ “bottom”_ then

21 Set width $w_{i}=\mathop{\rm width}(Q_{i-1})$, height $h_{i}=A(i)/w_{i}$,
and place rectangle $R_{i}$ exactly on top of $Q_{i-1}$;

22 Set $\mbox{direction}=$ “left”;

23 else

24 Set height $h_{i}=\mathop{\rm height}(Q_{i-1})$, width $w_{i}=A(i)/h_{i}$,
and place rectangle $R_{i}$ exactly on the right side of $Q_{i-1}$;

25 Set $\mbox{direction}=$ “top”;

26 end if

27 Set $Q_{i}=Q_{i-1}\cup R_{i}$;

28

29 end for

30 Set $R=Q_{n}$;

31 Rotate $R$ and the partition $R_{1},...,R_{n}$ for $90^{\circ}$
counterclockwise if $\mathop{\rm width}(R)<\mathop{\rm height}(R)$;

32 return _ $R,R_{1},...,R_{n}$_;

33

34 end if

35

36 end if

Algorithm 3 Symmetric Spiral $(L)$ Generates a treemap of rectangles with the
given areas in a clockwise-outward-growing spiral pattern.

###  5.2 Square-Bundled Spiral Treemap Algorithm

Our next algorithm, Square-Bundled Spiral, remedies the skinny rectangle issue
by bundling a subset of rectangles throughout the algorithm and creating
square-like bundles. As in Symmetric Spiral, first sort the input areas in an
ascending order and place the first two rectangles with $R_{2}$ to the left of
$R_{1}$ in a way that their union has aspect ratio of 2 (i.e., $\rho_{s}=2$).
The changes in direction also follow the same procedure. However, instead of
placing each rectangle in a spiral pattern we place bundled square-like
rectangles in a spiral pattern. Bundles are formed in each step by finding a
subset of remaining rectangles that makes the bundle as close as possible to a
square—given that one side of the bundled rectangle is already fixed to one
side of the union of already-placed rectangles. This makes our treemap as
close as possible to the Fibonacci spiral, where each new box is a square with
an edge length equal to the width (height) of the union of the previously-
placed rectangles. The layout inside a bundle can be created using any
rectangular treemapping algorithm as a subroutine. In our implementation we
use Squarified. Our choice comes from our observations that for square or
square-like input regions Squarified has an advantage.

Pseudocode for Square-Bundled Spiral is shown in algorithm 4 and its
computational complexity is $\mathcal{O}(n\log n)$ due to the sorting step;
the rest of the algorithm runs in $\mathcal{O}(n)$. In algorithm 4 we also
follow a clockwise-outward-growing rotation for forming the spiral structure.

Input: A list of $n$ areas $L=\\{A_{1},A_{2},...,A_{n}\\}$.

Output: A rectangle $R$ partitioned into $n$ sub-rectangles
$R_{1},R_{2},...,R_{n}$ with areas $A_{1},A_{2},...,A_{n}$ such that
$\mathop{\rm Area}\nolimits(R)=\sum_{i=1}^{n}A_{i}$.

/* *********************************************** */

1 if  _$n=1$_ then

2 return _$R_{1}$_ ;

3

4 end if

5Sort the list of areas in ascending order and reindex the sorted areas as
$A_{1},A_{2},...,A_{n}$;

/* Ensuring $R_{1}$ and $R_{2}$ together form a bigger rectangle with aspect
ratio $\rho_{s}=2$. */

6 Set $h_{1}=h_{2}=\sqrt{(A_{1}+A_{2})/2}$, $w_{1}=A_{1}/h_{1}$, and
$w_{2}=A_{2}/h_{2}$;

7 Place $R_{2}$ on the left of $R_{1}$;

8 Let $Q_{2}=\Box(R_{1}\cup R_{2})$;

9 if  _$n=2$_ then

_10_ _ _ return _$Q_{2},R_{1},R_{2}$ ;_

11

12 end if

13Set $\mbox{direction}=$ “top”;

14 while  _$i\mathrel{\mathtt{!=}}n$_ do

15 if  _$\mbox{direction}=$ “top” or “bottom”_ then

16 Set $w_{b}=\mathop{\rm width}(Q_{i-1})$;

17 Set
$k=\operatorname*{arg\,min}_{k\in\\{i,...,n\\}}\left|w_{b}-\frac{\sum_{j=i}^{k}A_{j}}{w_{b}}\right|$;

18 Set $h_{b}=\sum_{j=i}^{k}A_{j}/w_{b}$;

19 if  _$\mbox{direction}=$ “top”_ then

20 Place rectangle $B=w_{b}\times h_{b}$ exactly on top of $Q_{i-1}$;

21 Set $\mbox{direction}=$ “right”;

22

23 else

24 Place rectangle $B=w_{b}\times h_{b}$ exactly below $Q_{i-1}$;

25 Set $\mbox{direction}=$ “left”;

26

27 end if

28

29 else

/* $\mbox{direction}=$ ‘‘right’’ or ‘‘left’’ */

30 Set $h_{b}=\mathop{\rm height}(Q_{i-1})$;

31 Set
$k=\operatorname*{arg\,min}_{k\in\\{i,...,n\\}}\left|h_{b}-\frac{\sum_{j=i}^{k}A_{j}}{h_{b}}\right|$;

32 Set $w_{b}=\sum_{j=i}^{k}A_{j}/h_{b}$;

33 if  _$\mbox{direction}=$ “right”_ then

34 Place rectangle $B=w_{b}\times h_{b}$ exactly on the right side of
$Q_{i-1}$;

35 Set $\mbox{direction}=$ “bottom”;

36

37 else

38 Place rectangle $B=w_{b}\times h_{b}$ exactly on the left side of
$Q_{i-1}$;

39 Set $\mbox{direction}=$ “top”;

40

41 end if

42

43 end if

44 Let $(R_{i},...,R_{k})={\sf Squarified}(B,\\{A_{i},...,A_{k}\\})$;

45 Set $Q_{i}=Q_{i-1}\cup\left(\cup_{j=i}^{k}R_{j}\right)$;

46 Set $i=k+1$;

47

48 end while

49Set $R=Q_{n}$;

50 Rotate $R$ and the partition $R_{1},...,R_{n}$ for $90^{\circ}$
counterclockwise if $\mathop{\rm width}(R)<\mathop{\rm height}(R)$;

51 return _ $R,R_{1},...,R_{n}$_;

Algorithm 4 Square-Bundled Spiral $(L)$ Generates a treemap of rectangles with
the given areas. In each iteration the algorithm bundles a group of areas and
places them all together in a way that (1) the blocks of bundled rectangles
form a clockwise outward growing spiral pattern and (2) the layout inside each
block is formed using a subroutine such as Squarified.

###  5.3 Strip-Bundled Spiral Treemap Algorithm

As an alternative approach for improving Symmetric Spiral, we also develop
Strip-Bundled Spiral. The key difference is how many rectangles we place at
each change in direction. By considering the side of the current union where
the next rectangle has to be placed as a strip with its width (height) fixed
with this side of the current union and its height (width) being flexible, we
can add additional rectangles one-by-one, using the flexibility of the strip,
to optimize the aspect ratio before changing the direction and moving to the
next side. As in Symmetric Spiral and Square-Bundled Spiral, we first sort the
areas in ascending order and add the first two rectangles with $\rho_{s}=2$.
In each step, we create a strip on the top, right, bottom, or left side of the
union of already-placed rectangles. We then add the remaining rectangles to
the strip in order until the maximum aspect ratio of the rectangles does not
further improve. Then we change direction, create the next strip, and repeat
this procedure until all rectangles are placed.

Pseudocode for Strip-Bundled Spiral is shown in algorithm 5 and its
computational complexity is also $\mathcal{O}(n\log n)$ due to the sorting
step; the rest of the algorithm runs in $\mathcal{O}(n)$. In algorithm 5 we
again follow a clockwise-outward-growing rotation for forming the spiral
structure.

Input: A list of $n$ areas $L=\\{A_{1},A_{2},...,A_{n}\\}$.

Output: A rectangle $R$ partitioned into $n$ sub-rectangles
$R_{1},R_{2},...,R_{n}$ with areas $A_{1},A_{2},...,A_{n}$ such that
$\mathop{\rm Area}\nolimits(R)=\sum_{i=1}^{n}A_{i}$.

/* *********************************************** */

1 if  _$n=1$_ then

2 return _$R_{1}$_ ;

3

4 end if

5Sort the list of areas in ascending order and reindex the sorted areas as
$A_{1},A_{2},...,A_{n}$;

/* Ensuring $R_{1}$ and $R_{2}$ together form a bigger rectangle with aspect
ratio $\rho_{s}=2$. */

6 Set $h_{1}=h_{2}=\sqrt{(A_{1}+A_{2})/2}$, $w_{1}=A_{1}/h_{1}$, and
$w_{2}=A_{2}/h_{2}$;

7 Place $R_{2}$ on the left of $R_{1}$;

8 Let $Q_{2}=\Box(R_{1}\cup R_{2})$;

9 if  _$n=2$_ then

_10_ _ _ return _$Q_{2},R_{1},R_{2}$ ;_

11

12 end if

13Set $\mbox{direction}=$ “top”;

14 while  _$i\mathrel{\mathtt{!=}}n$_ do

15 if  _$\mbox{direction}=$ “top” or “bottom”_ then

16 Set $w_{s}=\mathop{\rm width}(Q_{i-1})$;

17 Set
$k=\operatorname*{arg\,min}_{k\in\\{i,...,n\\}}\max_{j\in\\{i,...,k\\}}$

18
$\quad\left\\{\frac{(\sum_{j=i}^{k}A_{j}/w_{s})^{2}}{A_{j}}\,,\,\frac{A_{j}}{(\sum_{j=i}^{k}A_{j}/w_{s})^{2}}\right\\}$;

19 Set $h_{s}=\sum_{j=i}^{k}A_{j}/w_{s}$;

20 if  _$\mbox{direction}=$ “top”_ then

21 Place rectangle $S=w_{s}\times h_{s}$ exactly on top of $Q_{i-1}$ and form
$Q_{i}$;

22 Slice $S$ into rectangles $R_{i},...,R_{k}$ with vertical cuts from left to
right with areas $A_{i},...,A_{k}$;

23 Set $\mbox{direction}=$ “right”;

24

25 else

26 Place rectangle $S=w_{s}\times h_{s}$ exactly below $Q_{i-1}$ and form
$Q_{i}$;

27 Slice $S$ into rectangles $R_{i},...,R_{k}$ with vertical cuts from right
to left with areas $A_{i},...,A_{k}$;

28 Set $\mbox{direction}=$ “left”;

29

30 end if

31

32 else

/* $\mbox{direction}=$ ‘‘right’’ or ‘‘left’’ */

33 Set $h_{s}=\mathop{\rm height}(Q_{i-1})$;

34 Set
$k=\operatorname*{arg\,min}_{k\in\\{i,...,n\\}}\max_{j\in\\{i,...,k\\}}$

35
$\quad\left\\{\frac{(\sum_{j=i}^{k}A_{j}/h_{s})^{2}}{A_{j}}\,,\,\frac{A_{j}}{(\sum_{j=i}^{k}A_{j}/h_{s})^{2}}\right\\}$;

36 Set $w_{s}=\sum_{j=i}^{k}A_{j}/h_{s}$;

37 if  _$\mbox{direction}=$ “right”_ then

38 Place rectangle $S=w_{s}\times h_{s}$ exactly on the right side of
$Q_{i-1}$ and form $Q_{i}$;

39 Slice $S$ into rectangles $R_{i},...,R_{k}$ with horizontal cuts from top
to bottom with areas $A_{i},...,A_{k}$;

40 Set $\mbox{direction}=$ “bottom”;

41 else

42 Place rectangle $S=w_{s}\times h_{s}$ exactly on the left side of $Q_{i-1}$
and form $Q_{i}$;

43 Slice $S$ into rectangles $R_{i},...,R_{k}$ with horizontal cuts from
bottom to top with areas $A_{i},...,A_{k}$;

44 Set $\mbox{direction}=$ “top”;

45 end if

46

47 end if

48

49 end while

50Set $R=Q_{n}$;

51 Rotate $R$ and the partition $R_{1},...,R_{n}$ for $90^{\circ}$
counterclockwise if $\mathop{\rm width}(R)<\mathop{\rm height}(R)$;

52 return _ $R,R_{1},...,R_{n}$_;

53

Algorithm 5 Strip-Bundled Spiral $(L)$ Generates a treemap of rectangles with
the given areas drawn in a clockwise outward growing spiral pattern. In each
iteration, rectangles are added as needed to minimize the total perimeter.

###  5.4 Comparison of Spiral Algorithms

Here we compare the results of the above three spiral algorithms with
Squarified, i.e., one of the best existing algorithms, with respect to aspect
ratio, as shown in e.g., [27, 23]. As previously see in [27] and we observe it
here too it can also perform reasonably well on stability depending on the
data set and the measure of stability. Since the main objective of all four
algorithms is to minimize aspect ratio, we examine the maximum aspect ratio
(maxAR). We also compare their stability using the maximum Hausdorff distance
(maxHD). (Section 6 provides a more comprehensive comparison.)

Fig. 9 illustrates the output treemaps of our spiral algorithms compared with
Squarified on a single level tree of 60 nodes with random weights. It is clear
that Square-Bundled Spiral and Strip-Bundled Spiral are more visually
appealing than Symmetric Spiral. Here, both improved spiral algorithms score
better on aspect ratio and stability than Squarified. Symmetric Spiral is
particularly bad on aspect ratio, as expected, but better than Squarified and
the other two spiral algorithms on stability.

Symmetric Spiral
maxAR = 30.01

Square-Bundled Spiral
maxAR = 2.35

Strip-Bundled Spiral
maxAR = 1.98

Squarified
maxAR = 2.69

Figure 6: Our three spiral treemap algorithms compared with Squarified for
making a rectangular treemap. The data shown is a single level tree of 60
randomly-weighted nodes. Bundled rectangles are shown using thicker lines.
Symmetric Spiral has the worst maximum aspect ratio (maxAR), but our other
spiral algorithms beat Squarified. They also have better maximum Hausdorff
distances (maxHD) than Squarified, with Symmetric Spiral doing best. The best
and second-best values are shown using color.

Another example in Fig. 7 shows treemaps of the number of COVID-19 diagnosed
cases in 52 different U.S. states and territories as of 2020-05-20, generated
using the same four algorithms. The data is collected from the Center for
Disease Control and Prevention (CDC). In this example, Squarified has the best
aspect ratio with Strip-Bundled Spiral a close second. All of our spiral
algorithms score better than Squarified for stability. Although Symmetric
Spiral created poor aspect ratios, in this application it may be preferred to
the other approaches as it may be easier to follow the sorted order that
actually matters more in this application.

Finally, these examples also demonstrate our expectation that Square-Bundled
Spiral is the closest to the Fibonacci spiral as the the distribution of the
edge length of the blocks are closer to the Fibonacci sequence. One could try
to study the impact of choices other than Squarified for the layout inside
each bundled block.

Symmetric Spiral
maxAR = 21.07

Square-Bundled Spiral
maxAR = 5.26

Strip-Bundled Spiral
maxAR = 2.20

Squarified
maxAR = 2.00

Figure 7: Our three spiral treemap algorithms compared with Squarified for
making a rectangular treemap. The data shown is the count of diagnosed cases
of COVID-19 in 52 different U.S. states and territories from the CDC as of
2020-05-20. Squarified has the best maximum aspect ratio (maxAR), followed by
Strip-Bundled Spiral. However, our spiral algorithms have better maximum
Hausdorff distances (maxHD). The best and second-best values are shown using
color. Note: we are not advocating this visualization for pandemic data.

##  6 Experiments and Results

Moving beyond usage examples, we here computationally compare treemap
algorithms based on aspect ratio and stability. We consider the following
evaluation criteria. For aspect ratio: total perimeter, maximum and average
aspect ratio (maxAR and avgAR), and area-weighted average aspect ratio (AWAR).
For stability: the maximum and average Hausdorff distance (maxHD and avgHD).

As discussed in Section 2.3, we compare our algorithms vs. Optimization Model
and the best-of-breed alternative: Squarified [17], that its superior quality,
considering aspect ratio measure, is demonstrated by extensive computational
results summarized in Fig. 8 – Fig. 11 in [23] and Fig. 21 and Fig. 26 in the
paper [27]. It is also clear from [27], as we observe it here too, it can also
perform reasonably well on stability depending on the data set and the measure
of stability. We also compare our results with the more recent algorithm
Divide & Conquer [4] that follows a similar approach and performs well when
compared to Squarified. Moreover, again as explained Section 2.3, we skip
space-filling curve-based algorithms for this comparison as they aim to to
preserve order and maximize readability and stability and generally perform
poorly with respect to aspect ratio metrics, as shown in [9, 12, 27, 23]. To
make the optimization results comparable with the algorithmic results, we set
all parameters in our Optimization Model to be zero.

We generated 25 random test problems for the comparison. These are listed in
synthetic_data.csv in the supplemental material at osf.io (hyperlink)
222osf.io/y8sgm/view_only=4e5edb49f893410a866f99fcf4e71cb5 and a table in the
appendices at osf.io (hyperlink). Since treemapping is NP-hard and finding an
optimal solution for large problems is challenging, we avoided cases with more
than 12 sub-regions. This is to ensure we can include Optimization Model in
the comparison. To further ease visual comparison, each weighted tree in our
problems has a height of 1. Deeper trees can be easily laid out by running
each of the algorithms recursively, as shown in Section 7.2.

In order to analyze the stability of treemaps constructed by each algorithm,
we build the treemaps for each sample, then perturb the input areas for a few
rounds in three level of perturbation, small, medium, and high. Furthermore,
we built new treemaps with new areas and calculated the Hausdorff Distance
between the pairs of rectangles in two treemaps. In small level of
perturbation we added a random variable between 0 and 1 multiplied by 0.01 to
the previous area then we normalized them to have area equal to 1. For medium
and high level of perturbation we did the same but instead of 0.01 we used
0.05 and 0.1.

TABLE I: The best and second-best value in each column is shown using color. Detailed results can be found in a table in the appendices at osf.io (hyperlink). All optimization parameters are set to be zero. We set $c=2$ in our modified divided and conquer approach. The three spiral algorithms are considered for two cases, when $\rho_{s}=2$ and $\rho_{s}=\phi=1.618$. The last three rows show the difference between the spiral averages (average for $\rho_{S}=\phi=1.618$ $-$ average for $\rho_{s}=2$) in percentage. The green color shows improvement and the red color shows deterioration.  Approach | Perimeter | maxAR | avgAR | AWAR | maxHD | avgHD
---|---|---|---|---|---|---
Optimization Model | 10.7257 | 1.7584 | 1.3211 | 1.3014 | – | –
Squarified [17] | 10.8738 | 2.9940 | 1.6452 | 1.4706 | 0.4512 | 0.2135
Divide & Conquer [4] | 10.9392 | 3.0372 | 1.6906 | 1.5735 | 1.2278 | 0.7535
Modified D&C ($c=2$) | 10.9021 | 2.5931 | 1.6231 | 1.5374 | 1.2268 | 0.7557
Dynamic Programming | 10.8136 | 2.6512 | 1.5221 | 1.3935 | 0.5222 | 0.2346
Symmetric Spiral $(\rho_{s}=2)$ | 12.3607 | 5.4034 | 2.7052 | 3.0156 | 0.5325 | 0.2410
Square-Bundled Spiral $(\rho_{s}=2)$ | 11.2379 | 3.2675 | 1.7874 | 1.8639 | 0.6808 | 0.2984
Strip-Bundled Spiral $(\rho_{s}=2)$ | 11.2122 | 3.5765 | 1.7559 | 1.8089 | 0.5670 | 0.2682
Symmetric Spiral $(\rho_{s}=1.618)$ | 12.2727 | 5.0748 | 2.6751 | 2.9747 | 0.4883 | 0.2258
Square-Bundled Spiral $(\rho_{s}=1.618)$ | 11.2149 | 3.6698 | 1.8116 | 1.8135 | 0.8287 | 0.3607
Strip-Bundled Spiral $(\rho_{s}=1.618)$ | 11.2908 | 3.9746 | 1.8568 | 1.7897 | 0.5481 | 0.2664
Symmetric Spiral $(\rho_{s}=1.618-\rho_{s}=2)$ | -0.71% | -6.08% | -1.11% | -1.36% | -8.30% | -6.31%
Square-Bundled Spiral $(\rho_{s}=1.618-\rho_{s}=2)$ | -0.20% | 12.31% | 1.35% | -2.70% | 21.72% | 20.87%
Strip-Bundled Spiral $(\rho_{s}=1.618-\rho_{s}=2)$ | 0.70% | 11.13% | 5.75% | -1.06% | -3.34% | -0.64%
Figure 8: Visual representation of the values in Table I to compare the size
of differences between treemap approaches with respect to metrics for aspect
ratio (Perimeter, maxAR, avgAr, AWAR) and stability (maxHD, avgHD).

Figure 9: Comparison of different algorithms regarding maximum and average
aspect ratios and maximum and average Hausdorff distances. The algorithms are
color coded and labeled with SQ (Squarified [17]), DC (Divide & Conquer [4]),
MDC (Modified D&C), DP (Dynamic Programming), SS (Symmetric Spiral), SQBS
(Square-Bundled Spiral), STBS (Strip-Bundled Spiral). We see that taking both
metrics into consideration, our DP performs the best. Our MDC beats both DC
and SQ on aspect ratio measure but performs weaker that SQ on stability. Our
two bundled spiral algorithms perform relatively good with the respect to both
maximum and average criteria. The symmetric spiral algorithm performs really
well on stability but really weak on aspect ratio. For SS we used
$\rho_{s}=\rho_{s}=\phi=\frac{1+\sqrt{5}}{2}\simeq 1.618$ and for the bundled
spiral we used the results from $\rho_{s}=2$.

The experimental results are summarized in Table I and Fig. 8, with individual
problem results in a table in the appendices at osf.io (hyperlink). Our
results show that Optimization Model is the best performer on all aspect ratio
measures—in some cases by wide margins. This is despite only optimizing for
total perimeter. Thus, we recommend Optimization Model be used as a benchmark
against which more computationally efficient approaches to optimizing for
aspect ratio can be compared, at least for reasonably sized problems. Since
our objective function is defined for perimeter (and consequently for aspect
ratios) and does not aim to produce stable treemaps, we skip the stability
performance of Optimization Model. However, as we discussed the flexibility of
our optimization model in Section 3, it could be possible to make a trade-off
between perimeter (aspect ratio) and stability but it is beyond the scope of
this paper.

For all measures, our Dynamic Programming outperforms Divide & Conquer [4] by
wide margins. This makes sense because it explores a larger set of possible
layouts. Our Dynamic Programming performs considerably better than Squarified
[17] on aspect ratio measures and only slightly weaker on stability measures.
This is besides the fact that the input region in 52% of our test problems was
a unit box which favors Squarified [17]. Dynamic Programming found the optimal
solution in 3 out 25 test problems, which is also a certificate to show that
these 3 problems had sliceable optimal solutions. Our Modified D&C outperforms
Divide & Conquer [4] on all but one measure and beats Squarified [17] by a
wide margin on maxAR measure. As expected our modification to the divide and
conquer approach of [4] shows its most significance on the maximum aspect
ratio which amounts to more than 17%. Our Dynamic Programming and Modified D&C
significantly improve on Divide & Conquer [4], despite the fact that in our
test problems we did not consider any extreme instance, as described in
Section 4.2, for which Divide & Conquer of [4] would perform particularly
weak.

As we expected, our spiral algorithms perform much better on stability
measures than aspect ratio measures. Symmetric Spiral performs particularly
weak on total perimeter and maxAR, due to stretching some rectangles. The
modified spiral algorithms Square-Bundled Spiral and Strip-Bundled Spiral
perform better on the aspect ratio measures. However, they perform weaker than
the non-spiral approaches. This is because (1) the sub-regions placed last are
more prone to poor aspect ratios and (2) the sub-regions are sorted in
ascending order of their areas giving more weight to those sub-regions placed
last. Stability analysis shows that all of our spiral algorithms generally
perform very well, which was again expected due to the packing framework and
spiral structure. By following a spiral structure, we believe they also
provide additional aesthetic appeal vs. other approaches. They maximize
_symmetry_ and _fractal-like patterns_ in the treemaps. It should be also
mentioned that removing the sorting step, we can easily modify these
algorithms to make them order-preserving. However, this may come at some cost
on the side of aspect ratios. One could consider evaluation metrics such as
readability measure introduced in [35] and the Fractal Value as defined in Eq.
(1) in [36], and evaluate the quality of our spiral algorithms that way.

We should also mention that in some of our test problems, our spiral
algorithms performed better than all other approaches including Optimization
Model even on the optimization objective (total perimeter). This is because
spiral algorithms are not restricted to the input container. Since this lack
of restriction to input region can lead to both significant improvements or
deterioration, we can claim that the performance of our spiral algorithms
highly depend on the problem instances. They performed weaker on average on
our test problems, although they were able to find solutions even better than
our Optimization Model on some instances. However, they should be seen as
alternatives that have the potential to generate superior results depending on
the problem instance.

In our spiral algorithms, an adjustable parameter $\rho_{s}$ sets the aspect
ratio of the first two placed rectangles. To mimic the Fibonacci/Golden spiral
we set $\rho_{s}=2$. To check the sensitivity of the algorithm to
$\rho_{s}$—while still approximating a golden spiral—we tried the golden
ratio, i.e., $\rho_{s}=\phi=\frac{1+\sqrt{5}}{2}\simeq 1.618$, and tested the
aforementioned data & measures. The last three rows of Table I show that this
change led to mixed results; Symmetric Spiral is improved on all metrics,
while Square-Bundled Spiral and Strip-Bundled Spiral are improved on some
metrics and deteriorated on some others. The changes in stability metrics on
both sides were significant. More sensitivity analysis could be done by
setting $\phi\leq\rho_{s}\leq 2$, while maintaining the overall golden spiral
structure.

Besides the quality metrics, run time is also important to consider. Our
Modified D&C, Symmetric Spiral, Square-Bundled Spiral, and Strip-Bundled
Spiral have a time complexity of $\mathcal{O}(n\log n)$, as does the best-of-
breed Squarified [17] and Divide & Conquer [4]. The running time of our
Dynamic Programming, which as discussed earlier is designed for quality not
computational efficiency, is $\mathcal{O}(n^{3})$. All of our algorithms scale
very well, although to lesser degree for Dynamic Programming, as apparent by
these worst-case running times and the fact that the implementation time of
the quasilinear algorithms on all of our test cases including the 25 random
test problems, the examples of size 60 and 52 in Fig. 9 and Fig. 7 and the a
famous 220 leaf node example in Section 7.2, was between fractions of a second
to a few seconds, similar to that of Divide & Conquer [4] and Squarified [17].
This time for Dynamic Programming increases to a few minutes.

##  7 Usage Examples

Here we present several usage examples to demonstrate the utility of our
treemap algorithms on realistic data, in contrast to the random data in our
computational experiments. All of these datasets are available at osf.io
(hyperlink).

###  7.1 Single Level Weighted Trees

We previously showed treemaps of single level weighted trees. This is to ease
comparisons, but deeper trees can be laid out via recursive application as we
will see in Section 7.2.

Stock Market—Stock market capitalization by sector has long been used as an
example for treemap algorithms, starting with Wattenberg’s Map of the Market
[31]. Our data is from the U.S. Stock Market after closing on 2020-12-18.
Figs. 4(a) and 4(b) and Figs. 5(i), 5(j), 5(l) and 5(k) show the associated
treemaps using our Optimization Model and the three divide and conquer
approaches.

U.S. Census—From the 2010 U.S. Census data we extracted 12 states in the
Midwest. The treemaps in Figs. 4(c) and 4(d) and Figs. 5(m), 5(n), 5(p) and
5(o) show the proportion of the total population that each of these states
contributes. The treemaps again use Optimization Model and the three divide
and conquer approaches.

COVID-19—Similar to the state population data, this example shows the
proportion of the total diagnosed cases of COVID-19 there were in each of the
52 U.S. States and territories as of 2020-05-20, according to the CDC. We show
this data in Fig. 7 using our three spiral approaches.

###  7.2 Multiple Level Weighted Trees

Similar to most other treemap algorithms, our proposed algorithms are proposed
for the single level trees but can be easily applied to multi-level trees as
well. This is straightforward for our divide and conquer and dynamic
programming algorithms as they are based on a subdivision approach and the
space for the parent is formed prior to forming the space for children.
However, our spiral algorithms that follow a packing approach require a bit of
explanation. We start from the bottom level and construct the rectangles for
immediate parents of the the leaf nodes following our spiral structure. Once
we have all the rectangles in the next level constructed, we make the
rectangles for their parents and recursively iterate this until the rectangle
for the root is formed. The only thing to consider here is that we will only
set $\rho_{s}=2$ or $\rho_{s}=\frac{1+\sqrt{5}}{2}$ at the bottom level and
relax this step for the higher levels. Note that we can also do this in
reverse direction and start from the root and work towards the bottom level.
We could also start from any middle level and work towards both directions of
the tree. However, we must fix the aspect ratio of the initial two rectangles
only in the level we start. This is to avoid having unused spaces in the
treemap.

Here, we will show the behavior of our treemap algorithms on a large
unbalanced height-4 tree with 220 leaf nodes. We use the Flare data. Flare
[72] is an ActionScript library for making web-based interactive Flash
visualizations. It is the spiritual successor to the Prefuse [73] Java library
and an early predecessor of D3[74]. The nodes in our tree are the ActionScript
3 classes in the library, arranged by the class hierarchy. Each node has a
weight for the size of the class. This data is widely available as part of
many online visualizations,333observablehq.com/@d3/hierarchical-edge-
bundling#file-readme-flare-imports-
json,444vega.github.io/editor/#/examples/vega/tree-
layout,555observablehq.com/@mahog/vega-tutorial-2-working-with-trees-
solution,666vega.github.io/editor/#/examples/vega/radial-tree-
layout,777vega.github.io/editor/#/examples/vega/circle-
packing,888vega.github.io/editor/#/examples/vega/sunburst,999observablehq.com/@mahog/vega-
tutorial-2-working-with-trees-solution and in particular treemaps generated
with various algorithms including Slice-and-Dice and
Squarified.101010observablehq.com/@d3/treemap?collection=@d3/d3-hierarchy,111111vega.github.io/editor/#/examples/vega/treemap

In Fig. 10 we show treemaps of the Flare data generated by our algorithms,
Squarified, and Divide & Conquer. See the figure caption for a comparative
discussion. We exclude Optimization Model due to long run time. For spiral
algorithms we illustrate the results for $\rho_{s}=2$. Table II shows the
comparison of metrics between the algorithms on this large data set. Our
Dynamic Programming still provides the best overall performance on this data
set.

TABLE II: Comparison of the metrics between the algorithms for the large unbalanced height-4 weighted tree of Flare [72] visualization library class hierarchy containing 220 leaf nodes. The best and second-best value in each column is shown using color. We set $c=2$ in our modified divided and conquer approach. The three spiral algorithms are considered for two cases, when $\rho_{s}=2$ and $\rho_{s}=\phi=1.618$.  Approach | Perimeter | maxAR | avgAR | AWAR | maxHD | avgHD
---|---|---|---|---|---|---
Squarified [17] | 53.2894 | 11.1962 | 1.5218 | 1.4025 | 0.9941 | 0.3669
Divide & Conquer [4] | 53.7136 | 5.4250 | 1.6539 | 1.5832 | 0.7004 | 0.3068
Dynamic Programming | 52.8362 | 7.7917 | 1.3788 | 1.3449 | 1.2388 | 0.5172
Modified D&C | 53.7366 | 5.6814 | 1.6167 | 1.6278 | 1.0451 | 0.4449
Symmetric Spiral $(\rho_{s}=2)$ | 75.1244 | 274.9278 | 15.9498 | 6.696 | 0.9191 | 0.4248
Square-Bundled Spiral $(\rho_{s}=2)$ | 54.4496 | 7.8461 | 1.7155 | 1.7913 | 1.1493 | 0.5066
Strip-Bundled Spiral $(\rho_{s}=2)$ | 55.4316 | 21.381 | 1.8899 | 2.0744 | 1.1757 | 0.5305
Symmetric Spiral $(\rho_{s}=1.618)$ | 74.2520 | 274.9278 | 15.8101 | 6.4117 | 0.9838 | 0.4527
Square-Bundled Spiral $(\rho_{s}=1.618)$ | 58.1248 | 39.5781 | 3.9537 | 2.1383 | 1.3837 | 0.5508
Strip-Bundled Spiral $(\rho_{s}=1.618)$ | 56.9472 | 16.2207 | 3.2577 | 1.9992 | 1.1325 | 0.4437

Symmetric Spiral

Squarified

Divide & Conquer

Square-Bundled Spiral

Dynamic Programming

Modified D&C

Strip-Bundled Spiral

Figure 10: Comparison of our five treemap algorithms, Squarified, and Divide &
Conquer, each showing the Flare [72] visualization library class hierarchy.
The data is an unbalanced “height-4” weighted tree, with “220 leaf nodes”
representing classes with weights as the class size. We can see that Symmetric
Spiral made some unfortunate choices with regards to aspect ratio, in
particular for the many skinny children of the query$\rightarrow$methods class
(shown in the color , top). However, the Symmetric Spiral is much more
apparent than the spirals in the other spiral treemaps, where rectangles are
predominantly fat. The spiral nature becomes more readily visible when there
are many similar-weight siblings, e.g., the children and grandchildren of vis
(left in Square-Bundled Spiral, right in Strip-Bundled Spiral). All of our
approaches stand in stark contrast with Squarified, which pushes the smaller
rectangles to the top-right, e.g., the children of util ( ).

##  8 Conclusion

We present an Optimization Model and five new treemapping algorithms. We
believe that Optimization Model, which minimizes the total sub-rectangle
perimeter as the objective function, is the first optimization approach to
treemapping. Besides only having the total perimeter as the objective function
it performs the best on all of our aspect ratio measures. Our computational
experiments show superior results vs. Squarified [17] and Divide & Conquer
[4], on four metrics for aspect ratio. It also outperformed our five new
algorithms. As such, we recommend Optimization Model be used as a benchmark
for comparing future algorithms on aspect ratio related measures.

Our new Dynamic Programming and Modified D&C significantly improve on Divide &
Conquer [4] for almost all measures, albeit with additional computational
complexity for Dynamic Programming, despite avoiding the extreme instances for
which Divide & Conquer is particularly vulnerable.

The three proposed spiral algorithms had weaker performance on aspect ratio
measures but very good performance on stability. They were also able to find
solutions even better than our Optimization Model on aspect ratio metrics for
a few of instances. This is due to the lack of restriction to input region and
suggest that performance of our spiral algorithms is problem dependent. They
also provide an arrangement that mimics the Fibonacci/Golden spiral which we
believe is more appealing and could be easier to follow. However, user studies
are necessary to validate this claim.

In this paper we assumed that $\mathop{\rm AR}=1$ is the best for sub-
rectangles, although we pursued other aspect ratios for blocks of sub-
rectangles in our spiral algorithms to make the overall layout more appealing.
This is a uniformly accepted goal to make sub-rectangles as square as possible
[23]. However, as suggested by [3, 64] and many other works in other fields,
it could be more desirable to have aspect ratios close to 3/2 or the golden
ratio $\phi=\frac{1+\sqrt{5}}{2}\simeq 1.618$ for the sub-rectangles as well.
One future research direction is to consider the impact of this change in the
objective.

Here we only evaluated treemapping algorithms on 6 measures of aspect ratio
and stability. To further explore the strengths and weaknesses of these
algorithms, we encourage future researchers to use additional quality metrics
and more datasets. Furthermore, one could tweak different parts of the
proposed spiral algorithms, e.g., the sorting part, to investigate the
sensitivity of the output quality to such changes.

To our knowledge, all divide and conquer treemapping approaches, including
ours, initially sort the input areas and as such they do not preserve input
order. An avenue for future research would be algorithmically making a
tradeoff between aspect ratio, stability, and preserving order. A machine
learning approach similar to that of [75] could also help to achieve the right
trade-off.

Another interesting direction for future research is to consider equal areas
being laid out as convex polygonal subregions inside an input region that is
not necessarily a rectangle. Clearly, this is very easy when $R$ is a
rectangle. However, this becomes quite complex when $R$ is a general convex
region. An approach similar to that of [76] in partitioning a convex polygon
into equal area sub-regions could be adopted to incorporate the additional
objective of minimizing total perimeter of all sub-regions.

## Acknowledgments

The authors gratefully acknowledge support from a Tier-1 grant from
Northeastern University. The authors also thank Ben Shneiderman for his
valuable comments and Zachary Danziger for his efficient MATLAB function on
calculating Hausdorff distance.

## References

  * [1] B. Shneiderman, “Tree visualization with tree-maps: 2-d space-filling approach,” Working paper, 1991.
  * [2] ——, “Tree Visualization with Tree-Maps: 2-d Space-Filling Approach,” _ACM Transactions on Graphics_ , vol. 11, no. 1, pp. 92–99, 1992.
  * [3] N. Kong, J. Heer, and M. Agrawala, “Perceptual guidelines for creating rectangular treemaps,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 16, no. 6, pp. 990–998, 2010.
  * [4] J. Liang, Q. V. Nguyen, S. Simoff, and M. L. Huang, “Divide and conquer treemaps: Visualizing large trees with various shapes,” _Journal of Visual Languages & Computing_, vol. 31, pp. 104–127, 2015.
  * [5] K. Onak and A. Sidiropoulos, “Circular partitions with applications to visualization and embeddings,” in _Proc. Twenty-Fourth Annual Symposium on Computational Geometry_ , 2008, pp. 28–37.
  * [6] M. Balzer, O. Deussen, and C. Lewerentz, “Voronoi treemaps for the visualization of software metrics,” in _Proc. ACM Symposium on Software visualization_ , May 2005, pp. 165–172.
  * [7] M. Balzer and O. Deussen, “Voronoi treemaps,” in _IEEE Symposium on Information Visualization_ , ser. InfoVis, October 2005, pp. 49–56.
  * [8] H. Lü and J. Fogarty, “Cascaded treemaps: examining the visibility and stability of structure in treemaps,” in _Proc. Graphics Interface_ , 2008, pp. 259–266.
  * [9] Y. Tu and H.-W. Shen, “Visualizing changes of hierarchical data using treemaps,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 13, no. 6, pp. 1286–1293, 2007.
  * [10] S. Chaturvedi, C. Dunne, Z. Ashktorab, R. Zacharia, and B. Shneiderman, “Group-in-a-Box meta-layouts for topological clusters and attribute-based groups: space efficient visualizations of network communities and their ties,” _Computer Graphics Forum_ , vol. 33, no. 8, pp. 52–68, 2014.
  * [11] D. Auber, C. Huet, A. Lambert, B. Renoust, A. Sallaberry, and A. Saulnier, “Gospermap: Using a gosper curve for laying out hierarchical data,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 19, no. 11, pp. 1820–1832, 2013.
  * [12] S. Tak and A. Cockburn, “Enhanced spatial stability with Hilbert and Moore treemaps,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 19, no. 1, pp. 141–148, 2012.
  * [13] W. Scheibel, D. Limberger, and J. Döllner, “Survey of treemap layout algorithms,” in _Proceedings of the 13th international symposium on visual information communication and interaction_ , 2020, pp. 1–9.
  * [14] H.-J. Schulz, S. Hadlak, and H. Schumann, “The design space of implicit hierarchy visualization: A survey,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 17, no. 4, pp. 393–411, 2010.
  * [15] W. Scheibel, M. Trapp, D. Limberger, and J. Döllner, “A taxonomy of treemap visualization techniques.” in _VISIGRAPP (3: IVAPP)_ , 2020, pp. 273–280.
  * [16] B. Johnson and B. Shneiderman, “Tree-maps: a space-filling approach to the visualization of hierarchical information structures,” in _Proc. Visualization_ , 1991, pp. 284–291.
  * [17] M. Bruls, K. Huizing, and J. J. van Wijk, “Squarified treemaps,” in _Proc. Data Visualization_ , 2000, pp. 33–42.
  * [18] I. S. MacKenzie, “Fitts’ law as a research and design tool in human-computer interaction,” _Human–Computer Interaction_ , vol. 7, no. 1, pp. 91–139, 1992.
  * [19] B. Shneiderman and M. Wattenberg, “Ordered treemap layouts,” in _IEEE Symposium on Information Visualization_ , 2001, pp. 73–73.
  * [20] A. Sud, D. Fisher, and H.-P. Lee, “Fast dynamic voronoi treemaps,” in _2010 International Symposium on Voronoi Diagrams in Science and Engineering_ , 2010, pp. 85–94.
  * [21] K. Misue, P. Eades, W. Lai, and K. Sugiyama, “Layout adjustment and the mental map,” _Journal of Visual Languages & Computing_, vol. 6, no. 2, pp. 183 – 210, 1995.
  * [22] M. Wattenberg, “Visualizing the stock market,” in _Extended Abstracts on Human Factors in Computing Systems_ , ser. CHI EA, 1999, pp. 188–189.
  * [23] E. Vernier, M. Sondag, J. Comba, B. Speckmann, A. Telea, and K. Verbeek, “Quantitative comparison of time-dependent treemaps,” in _Computer Graphics Forum_ , vol. 39, no. 3. Wiley Online Library, 2020, pp. 393–404.
  * [24] J. Wood and J. Dykes, “Spatially ordered treemaps,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 14, no. 6, pp. 1348–1355, 2008\.
  * [25] S. Hahn, J. Trümper, D. Moritz, and J. Döllner, “Visualization of varying hierarchies by stable layout of voronoi treemaps,” in _2014 International Conference on Information Visualization Theory and Applications (IVAPP)_. IEEE, 2014, pp. 50–58.
  * [26] S. Hahn, J. Bethge, and J. Döllner, “Relative direction change-a topology-based metric for layout stability in treemaps.” in _VISIGRAPP (3: IVAPP)_ , 2017, pp. 88–95.
  * [27] M. Sondag, B. Speckmann, and K. Verbeek, “Stable treemaps via local moves,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 24, no. 1, pp. 729–738, 2018.
  * [28] W. Scheibel, C. Weyand, and J. Döllner, “Evocells-a treemap layout algorithm for evolving tree data.” in _VISIGRAPP (3: IVAPP)_ , 2018, pp. 273–280.
  * [29] Y. Yang, K. Zhang, J. Wang, and Q. V. Nguyen, “Cabinet Tree: an orthogonal enclosure approach to visualizing and exploring big data,” _Journal of Big Data_ , vol. 2, no. 1, p. 15, 2015.
  * [30] C. Fiedler, W. Scheibel, D. Limberger, M. Trapp, and J. Döllner, “Survey on user studies on the effectiveness of treemaps,” in _Proceedings of the 13th International Symposium on Visual Information Communication and Interaction_ , 2020, pp. 1–10.
  * [31] M. Wattenberg, “Map of the Market,” 1998, accessed on 2020-07-28, http://www.bewitched.com/marketmap.html.
  * [32] Q. V. Nguyen and M. L. Huang, “Enccon: an approach to constructing interactive visualization of large hierarchical data,” _Information Visualization_ , vol. 4, no. 1, pp. 1–21, 2005.
  * [33] F. Vernier and L. Nigay, “Modifiable treemaps containing variable-shaped units,” in _IEEE Information Visualization_ , 2000.
  * [34] B. Engdahl, “Ordered and unordered treemap algorithms and their applications on handheld devices,” Master’s thesis, Department of Numerical Analysis and Computer Science, Stockholm Royal Institute of Technology, 2005.
  * [35] B. B. Bederson, B. Shneiderman, and M. Wattenberg, “Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies,” _ACM Transactions on Graphics_ , vol. 21, no. 4, pp. 833–854, 2002.
  * [36] M. D’Ambros, M. Lanza, and H. Gall, “Fractal figures: Visualizing development effort for cvs entities,” in _3rd IEEE International Workshop on Visualizing Software for Understanding and Analysis_. IEEE, 2005, pp. 1–6.
  * [37] E. F. Vernier, J. L. D. Comba, and A. C. Telea, “A stable greedy insertion treemap algorithm for software evolution visualization,” in _Proc. 31st Conference on Graphics, Patterns and Images_ , ser. SIBGRAPI, 2018, pp. 158–165.
  * [38] M. J. Baker and S. G. Eick, “Space-filling software visualization,” _Journal of Visual Languages & Computing_, vol. 6, no. 2, pp. 119–133, 1995\.
  * [39] J. J. van Wijk and H. van de Wetering, “Cushion treemaps: Visualization of hierarchical information,” in _Proc. 1999 IEEE Symposium on Information Visualization_ , ser. InfoVis, 1999, pp. 73–78.
  * [40] R. Vliegen, J. J. van Wijk, and E.-J. van der Linden, “Visualizing business data with generalized treemaps,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 12, no. 5, pp. 789–796, 2006.
  * [41] F. S. Duarte, F. Sikansi, F. M. Fatore, S. G. Fadel, and F. V. Paulovich, “Nmap: A novel neighborhood preservation space-filling algorithm,” _IEEE transactions on visualization and computer graphics_ , vol. 20, no. 12, pp. 2063–2071, 2014.
  * [42] R. Reitsma, S. Trubin, and E. Mortensen, “Weight-proportional space partitioning using adaptive voronoi diagrams,” _Geoinformatica_ , vol. 11, no. 3, pp. 383–405, 2007.
  * [43] A. Nocaj and U. Brandes, “Computing voronoi treemaps: Faster, simpler, and resolution-independent,” _Computer Graphics Forum_ , vol. 31, no. 3pt1, pp. 855–864, 2012.
  * [44] ——, “Organizing search results with a reference map,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 18, no. 12, pp. 2546–2555, 2012.
  * [45] D. P. Tua, R. Minelli, and M. Lanza, “Voronoi evolving treemaps,” in _2021 Working Conference on Software Visualization (VISSOFT)_. IEEE, 2021, pp. 1–5.
  * [46] Y.-C. Wang, J. Liu, F. Lin, and H.-S. Seah, “Generating orthogonal voronoi treemap for visualization of hierarchical data,” in _Computer Graphics International Conference_. Springer, 2020, pp. 394–402.
  * [47] Y. C. Wang, Y. Xing, and J. Zhang, “Voronoi treemap in manhattan distance and chebyshev distance,” _Information Visualization_ , vol. 22, no. 3, pp. 246–264, 2023.
  * [48] Q. V. Nguyen and M. L. Huang, “Space-optimized tree: a connection+ enclosure approach for the visualization of large hierarchies,” _Information Visualization_ , vol. 2, no. 1, pp. 3–15, 2003.
  * [49] M. Wattenberg, “A note on space-filling visualizations and space-filling curves,” in _IEEE Symposium on Information Visualization_ , ser. InfoVis, 2005, pp. 181–186.
  * [50] M. Sondag, W. Meulemans, C. Schulz, K. Verbeek, D. Weiskopf, and B. Speckmann, “Uncertainty treemaps,” in _2020 IEEE Pacific Visualization Symposium (PacificVis)_. IEEE, 2020, pp. 111–120.
  * [51] H. Nagamochi and Y. Abe, “An approximation algorithm for dissecting a rectangle into rectangles with specified areas,” _Discrete Applied Mathematics_ , vol. 155, no. 4, pp. 523–537, 2007.
  * [52] O. Beaumont, V. Boudet, F. Rastello, and Y. Robert, “Partitioning a square into rectangles: NP-completeness and approximation algorithms,” _Algorithmica_ , vol. 34, no. 3, pp. 217–239, 2002.
  * [53] Q. T. Bui, T. Vidal, and M. H. Hà, “On three soft rectangle packing problems with guillotine constraints,” _Journal of Global Optimization_ , vol. 74, no. 1, pp. 45–62, 2019.
  * [54] M. de Berg, K. Onak, and A. Sidiropoulos, “Fat polygonal partitions with applications to visualization and embeddings,” _arXiv preprint arXiv:1009.1866_ , 2010.
  * [55] ——, “Fat polygonal partitions with applications to visualization and embeddings,” _Journal of Computational Geometry_ , vol. 4, no. 1, pp. 212–239, 2013.
  * [56] M. de Berg, B. Speckmann, and V. van der Weele, “Treemaps with bounded aspect ratio,” _Computational Geometry_ , vol. 47, no. 6, pp. 683–693, 2014.
  * [57] O. Beaumont, V. Boudet, F. Rastello, and Y. Robert, “Matrix multiplication on heterogeneous platforms,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 12, no. 10, pp. 1033–1051, 2001.
  * [58] H. Zhao and L. Lu, “Variational circular treemaps for interactive visualization of hierarchical data,” in _2015 IEEE Pacific Visualization Symposium (PacificVis)_. IEEE, 2015, pp. 81–85.
  * [59] E. Carrizosa, V. Guerrero, and D. R. Morales, “Visualizing proportions and dissimilarities by space-filling maps: a large neighborhood search approach,” _Computers & Operations Research_, vol. 78, pp. 369–380, 2017\.
  * [60] O. Fried, S. DiVerdi, M. Halber, E. Sizikova, and A. Finkelstein, “Isomatch: Creating informative grid layouts,” in _Computer Graphics Forum_ , vol. 34, no. 2. Wiley Online Library, 2015, pp. 155–166.
  * [61] A. Fügenschuh and M. Fügenschuh, “Integer linear programming models for topology optimization in sheet metal design,” _Mathematical Methods of Operations Research_ , vol. 68, pp. 313–331, 2008.
  * [62] A. Fügenschuh, K. Junosza-Szaniawski, and Z. Lonc, “Exact and approximation algorithms for a soft rectangle packing problem,” _Optimization_ , vol. 63, no. 11, pp. 1637–1663, 2014.
  * [63] A. Fügenschuh, W. Hess, L. Schewe, A. Martin, and S. Ulbrich, “Verfeinerte modelle zur topologie-und geometrie-optimierung von blechprofilen mit kammern,” in _Sonderforschungsbereich 666_ , 2008, pp. 17–28.
  * [64] L. Lu, S. Fan, M. Huang, W. Huang, and R. Yang, “Golden rectangle treemap,” in _Journal of Physics: Conference Series_ , vol. 787, no. 1, 2017, p. 012007\.
  * [65] K. Boussora and S. Mazouz, “The use of the golden section in the great mosque at kairouan,” _Nexus Network Journal_ , vol. 6, no. 1, pp. 7–16, 2004.
  * [66] A. Dahar and R. Alipour, “Geometrical analysis of architecture of sheik lotfollah mosque to find the geometrical relations between its prayer hall and the entrance,” _BAGH-E NAZAR_ , vol. 10, no. 26, pp. 33–40, 2013.
  * [67] J. Elliot, _Mirrors of the Unseen: Journeys in Iran_. Pan Macmillan, 2007, pp. 277,284.
  * [68] P. Foutakis, “Did the Greeks build according to the golden ratio?” _Cambridge Archaeological Journal_ , vol. 24, no. 1, pp. 71–86, 2014.
  * [69] M. Livio, “The golden ratio and aesthetics,” _Plus Magazine_ , 1 November 2002, https://plus.maths.org/content/os/issue22/features/golden/index.
  * [70] A. J. Frost and R. R. Prechter, _Elliott wave principle: key to market behavior_. New Classics Library, 1995.
  * [71] J. Kiefer, “Sequential minimax search for a maximum,” _Proc. American Mathematical Society_ , vol. 4, no. 3, pp. 502–506, 1953.
  * [72] J. Heer, “Flare: Data visualization for the web,” 2007, accessed on 2020-12-11, https://blokt.com/tool/prefuse-flare.
  * [73] J. Heer, S. K. Card, and J. A. Landay, “Prefuse: A toolkit for interactive information visualization,” in _Proc. SIGCHI Conference on Human Factors in Computing Systems_ , ser. CHI ’05, 2005, p. 421–430.
  * [74] M. Bostock, V. Ogievetsky, and J. Heer, “D3: Data-driven documents,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 17, no. 12, pp. 2301–2309, 2011.
  * [75] J. Bethge, S. Hahn, and J. Döllner, “Improving layout quality by mixing treemap-layouts based on data-change characteristics,” in _Proceedings of the Conference on Vision, Modeling and Visualization_ , 2017, pp. 69–76.
  * [76] J. G. Carlsson, M. Behroozi, and X. Li, “Geometric partitioning and robust ad-hoc network design,” _Annals of operations research_ , vol. 238, pp. 41–68, 2016.