TL;DR
This paper introduces a linear programming (LP) framework to create "stable" Demers cartograms—map-like visualizations where regions are represented by squares sized according to data. By enforcing relative position constraints, the method ensures that as data changes over time, the squares move predictably and smoothly, preserving the viewer's "mental map" without any overlapping during transitions.
What Problem Does This Paper Address?
Cartograms are powerful tools for visualizing data (like population or GDP) by scaling geographic regions based on their values. Demers cartograms specifically use squares to represent regions, making it easy for viewers to compare areas.
However, a major challenge arises with time-varying or multivariate data. If you create a separate cartogram for every year of a census, the squares might "jump" to entirely different positions from one frame to the next. This destroys the viewer's mental map—the internal spatial model we use to understand where regions are relative to one another. Existing methods often struggle to balance "cartogram quality" (keeping neighbors close) with "stability" (keeping the layout consistent over time).
Methods
The authors propose a novel approach using Linear Programming (LP) to optimize the layout of these squares.
- Separation Constraints: To maintain the geographic "feel," the algorithm extracts relative directions (north, south, east, west) from the original map. It then enforces these as hard constraints: if region A is north of region B on the real map, it must remain north (or at least not move south) of it in the cartogram.
- Objective Functions: The LP can be tuned to prioritize different goals:
- TOP: Minimizing the distance between topologically adjacent regions.
- ORG: Minimizing the distance from the square's center to its original geographic centroid.
- CNT: Minimizing the actual number of lost adjacencies (this requires Integer Linear Programming, which is more computationally intensive).
- Stability Implementations: To handle multiple datasets, they link the LPs for different time steps. They tested "Global" optimization (solving all time steps at once) versus "Iterative" optimization (solving one step based on the previous one).
- Leaders: Since squares of fixed sizes cannot always touch their neighbors (a mathematical limitation of planar graphs), the authors use "leaders"—orthogonal lines—to visually connect regions that should be adjacent but aren't touching.
Datasets
The researchers evaluated their method using two primary geographic structures:
- The Contiguous US (48 states): A highly structured map with large states in the west and many small states in the east.
- World Map: A more "unstructured" and complex set of adjacencies.
They applied these to real-world time-series data (2006–2016) including GDP, Population, Forest Area, and Drug Poisoning Mortality.
Key Insights and Ideas
- The Overlap-Free Guarantee: One of the most elegant findings is a lemma proving that any linear interpolation between two stable Demers cartograms (sharing the same constraints) is guaranteed to be overlap-free. This makes for perfectly smooth, legible animations.
- Strong vs. Weak Constraints: The authors distinguish between "weak" (basic relative order) and "strong" (additional constraints for non-adjacent regions) settings. They found that "strong" constraints significantly improve the preservation of relative directions but slightly increase the distance between neighbors.
- The Topology Proxy: Interestingly, while minimizing distance to the original origin (ORG) is often used as a proxy for quality in other map types, the authors found that for Demers cartograms, it actually performs poorly at maintaining the map's topology compared to their TOP objective.
Key Results
- Efficiency: On a standard laptop, the LP-based "Iterative" variants finished in seconds for the US map and under a minute for the World map.
- Stability vs. Quality: The proposed LP methods generally outperformed a baseline Force-Directed (FRC) method. While force-directed methods are common, they don't enforce separation constraints, often leading to "flipped" regions that confuse the viewer.
- Quantitative Performance: The "TOP-W-IT" variant (minimizing adjacency distance with weak constraints iteratively) emerged as a strong all-rounder, providing high-quality layouts with excellent stability scores.
Limitations and Future Work
- Computational Complexity of Adjacencies: While the LP is fast, the version that minimizes the number of lost adjacencies (CNT) is an Integer Linear Program. This proved to be "intractable" for the World map, running out of memory even with 48GB allocated.
- Human Perception: The metrics used (MADJ, MREL, etc.) are mathematical. The authors suggest that future work should involve human-centered studies to see if these "stable" layouts actually improve a user's ability to perform tasks like tracking a specific state's growth over a decade.
- Other Shapes: The current work is strictly for squares (Demers). Extending these stability proofs and LP formulations to rectangles or more complex polygons remains an open challenge.
Summary updated