Our method creates Voronoi treemap layouts optimized to preserve similarities between nodes, resulting in appropriate neighborhoods in the treemap visualization. For this example, we use a two-level hierarchy dataset of large countries with a population of > 50 Mio (+ Australia), grouped by their continents. First, we filter existing similarity between nodes, in this case, the geographic neighborhood between countries, to create similarity constraints. Next, Voronoi diagrams are initialized on each level using a combination of dimensionality reduction, matching, and cell swapping. During optimization, based on the constraints, an attraction force moves nodes towards other similar nodes, so their Voronoi cells share edges. The final Voronoi treemaps (c)-(d) show that most of the similarity constraints, representing geographical neighborhood, have been realized (see the “Interlocking” metaphor). Each continent is assigned a color, and countries of a continent have slightly varied colors from their neighbors.
Material
Abstract
Voronoi treemaps are used to depict nodes and their hierarchical relationships simultaneously. However, in addition to the hierarchical structure, data attributes, such as co-occurring features or similarities, frequently exist. Examples include geographical attributes like shared borders between countries or contextualized semantic information such as embedding vectors derived from large language models. In this work, we introduce a Voronoi treemap algorithm that leverages data similarity to generate neighborhood-preserving treemaps. First, we extend the treemap layout pipeline to consider similarity during data preprocessing. We then use a Kuhn-Munkres matching of similarities to centroidal Voronoi tessellation (CVT) cells to create initial Voronoi diagrams with equal cell sizes for each level. Greedy swapping is used to improve the neighborhoods of cells to match the data's similarity further. During optimization, cell areas are iteratively adjusted to their respective sizes while preserving the existing neighborhoods. We demonstrate the practicality of our approach through multiple real-world examples drawn from infographics and linguistics. To quantitatively assess the resulting treemaps, we employ treemap metrics and measure neighborhood preservation.