Abstract
Cartograms are popular for visualizing numerical data for map regions. Maintaining correct adjacencies is a primary quality criterion for cartograms. When there are multiple data values per region (over time or different datasets) shown as animated or juxtaposed cartograms, preserving the viewer's mental-map in terms of stability between cartograms is another important criterion. We present a method to compute stable Demers cartograms, where each region is shown as a square and similar data yield similar cartograms. We enforce orthogonal separation constraints with linear programming, and measure quality in terms of keeping adjacent regions close (cartogram quality) and using similar positions for a region between the different data values (stability). Our method guarantees ability to connect most lost adjacencies with minimal leaders. Experiments show our method yields good quality and stability.
Introduction
Cartograms are powerful tools for visualizing data, such as population or GDP, by scaling geographic regions based on their values. Demers cartograms specifically represent regions as squares, facilitating easy area comparisons for viewers. However, a significant challenge arises with time-varying or multivariate data. If separate cartograms are created for each time step, regions may "jump" to different positions, destroying the viewer's mental map—the internal spatial model used to understand relative regional positions.
This research addresses the balance between cartogram quality (maintaining neighbor proximity) and stability (consistent layout over time) through a novel linear programming (LP) framework.
Methodology
The proposed method utilizes Linear Programming to optimize square layouts while enforcing relative position constraints.
Separation Constraints and Objectives
To preserve geographic context, the algorithm extracts relative directions (north, south, east, west) from the original map. These are enforced as hard constraints: if region A is north of region B geographically, it must remain north of it in the cartogram. The LP can be tuned using different objective functions:
- TOP: Minimizes distance between topologically adjacent regions.
- ORG: Minimizes distance from a square's center to its original geographic centroid.
- CNT: Minimizes the number of lost adjacencies (requires Integer Linear Programming).
Stability and Leaders
To handle multiple datasets, the LPs for different time steps are linked. The researchers tested both "Global" optimization (solving all steps simultaneously) and "Iterative" optimization (solving one step based on the previous). Because squares of fixed sizes cannot always touch their neighbors, the method employs "leaders"—orthogonal lines—to visually connect regions that should be adjacent but are not touching.
Experimental Evaluation
The method was evaluated using the contiguous US (48 states) and a world map, applied to real-world time-series data including GDP, population, and forest area.
Key Results
- Efficiency: The iterative LP variants processed the US map in seconds and the world map in under a minute on standard hardware.
- Stability vs. Quality: The LP methods outperformed baseline force-directed methods, which often lead to confusing "flipped" regions because they lack hard separation constraints. The "TOP-W-IT" variant (minimizing adjacency distance with weak constraints iteratively) proved to be an effective all-rounder.
- Overlap-Free Guarantee: A key finding is that any linear interpolation between two stable Demers cartograms sharing the same constraints is guaranteed to be overlap-free, ensuring smooth and legible animations.
Conclusion and Future Work
The LP-based approach successfully generates stable Demers cartograms that preserve the viewer's mental map. While the TOP objective performs well, the CNT objective remains computationally intensive for complex maps. Future research will focus on human-centered studies to validate these mathematical stability metrics and extending the framework to non-square shapes like rectangles or complex polygons.
Summary updated