Algorithms for Coherent Rectangular Visualizations

Max Sondag

promotor: prof.dr. Bettina Speckmann (TU/e)
co-promotor: dr. Wouter Meulemans (TU/e)
Eindhoven University of Technology
Date: 30 November, 2020
Thesis: PDF


To gain insight into the large amounts of data that chronicle our life, work and world, we often turn to visualizations to use our powerful perceptual system for (parts of) the analysis. For a visualization to be effective, the visualization has to visually represent all properties of the data that the viewer requires for the task they want to perform. Moreover, an effective visualization has to be coherent: relations between data items are visually represented, and visible relations are present in the data. A coherent visualization thus prevents false patterns from emerging in the visualization, and preserves patterns that exist in the data. Our focus in this thesis lies on rectangular visualizations, that is, visualizations that use rectangles as their fundamental building blocks. We describe several new algorithms that transform data into coherent rectangular visualizations for four different data types.

We first study temporal coherence for treemaps, which visualize hierarchical data using nested rectangles whose areas match the data values. When the data varies over time, we can generate a treemap for each time step. The quality of a treemapping algorithm is then determined by two factors: (i) the visual quality, which indicates how well we can determine the values of the data for a single treemap and (ii) the temporal coherence or stability, which indicates how coherent the changes in the data are with the changes in the treemap. Ideally, small changes in the data should result in small changes in the treemap. We propose a novel stable treemapping algorithm that has high visual quality. Whereas existing treemapping algorithms generally recompute the treemap every time the input changes, our algorithm changes the layout of the treemap using only local modifications. This approach gives us direct control over the stability, and in contrast to existing treemapping algorithms, can also generate non-sliceable treemap layouts. We prove that using these non-sliceable layouts can result in treemaps of higher visual quality. To verify the efficacy of the new algorithm as well as existing treemapping algorithms, we perform an extensive quantitative evaluation of rectangular treemapping algorithms for time-varying hierarchical data. To this end, we first propose a new method to measure the stability of time-varying treemaps which explicitly considers the input data.  Additionally, we identify four representative features of datasets that influence the performance of treemapping algorithms. We use these features to propose a novel classification scheme for time-varying hierarchical datasets. We experimentally test the validity of this classification on a large number of datasets, and use this classification to compare and evaluate treemapping algorithms on a variety of datasets.

Second, we study the coherence between data and uncertainty when visualizing uncertain hierarchical data using treemaps. To visualize uncertainty in a treemap, we identify two key, but conflicting, requirements: (i) to easily assess the data value of a node in the hierarchy, the area of its rectangle should directly match its data value, and (ii) to ensure coherence and facilitate comparison between data and uncertainty, uncertainty must be encoded using the same visual variable as the data, that is, area. We present Uncertainty Treemaps which meet both requirements simultaneously using the novel concept of hierarchical uncertainty masks. We define a new cost function that measures the quality of Uncertainty Treemaps and show how to adapt existing treemapping algorithms to support uncertainty masks. Finally, we demonstrate the quality of our technique through a computational experiment on real-world datasets.

Third, we improve upon the spatial coherence of grid maps: spatial arrangements of simple tiles (often squares or hexagons) each of which represents a spatial element. An effective grid map is coherent with the underlying spatial dimension: the tiles maintain properties such as contiguity, neighborhoods and identifiability of the corresponding spatial elements, while the grid map as a whole maintains the global shape of the input. Of particular importance are salient local features of the global shape which need to be represented by tiles assigned to the appropriate spatial elements. State-of-the-art techniques can adequately deal only with simple cases, such as a close-to-uniform spatial dimension or global shapes that have few characteristic features. We introduce a simple fully-automated 3-step pipeline for computing high-quality coherent grid maps. Each step relies on well-established solutions: shape decomposition based on salient features, tile-based Mosaic Cartograms, and point-set matching.
We provide an implementation, demonstrate the efficacy of our approach on various complex datasets and compare it to the state-of-the-art.

Finally, we propose a new way to visualize spatial set data. We assume that the nodes of the sets are positioned on a grid. Each node is represented by a cell in the grid and each set is represented by a single connected polygon overlapping exactly those cells that correspond to the nodes in the set. For the case where there are two sets, we derive a necessary and sufficient condition to efficiently recognize whether we can represent each set with a single connected polygon. Additionally, we show that the visual complexity of the polygon in each cell can be bounded by a small constant.