On Minimizing Wiggle in Stacked Area Charts
Alexander Dobler, Martin Nöllenburg · 2025
Read On Minimizing Wiggle in Stacked Area Charts by Alexander Dobler, Martin Nöllenburg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-21175.txt.
Introduction
Alexander Dobler and Martin Nöllenburg study how hard it is to keep stacked area charts smooth, in a 2025 paper. In these charts, time series pile up as layers, and the vertical wobble of the borders between layers, called wiggle, hurts readability. Many quick methods exist to cut wiggle, but nobody had settled how hard the problem itself is.
The pair proves that several versions of wiggle minimization are NP-hard and even hard to approximate well. They also give an exact method based on mixed-integer programming and test it against a leading quick method. A stripped-down special case, ordering numbers to keep running totals small, carries its own hardness results that feed into the chart results.
Catalog record
| CREATOR | Alexander Dobler, Martin Nöllenburg |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-21175
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Minimizing Wiggle in Stacked Area Charts Alexander Dobler, Martin Nöllenburg Abstract Stacked area charts are a widely used visualization technique for numerical time series. The x x -axis represents time, and the time series are displayed as horizontal, variable-height layers stacked on top of each other. The height of each layer corresponds to the time series values at each time point. The main aesthetic criterion for optimizing the readability of stacked area charts is the amount of vertical change of the borders between the time series in the visualization, called wiggle . While many heuristic algorithms have been developed to minimize wiggle, the computational complexity of minimizing wiggle has not been formally analyzed. In this paper, we show that different variants of wiggle minimization are 𝖭𝖯 \mathsf{NP} -hard and even hard to approximate. We also present an exact mixed-integer linear programming formulation and compare its performance with a state-of-the-art heuristic in an experimental evaluation. Lastly, we consider a special case of wiggle minimization that corresponds to the fundamentally interesting and natural problem of ordering a set of numbers as to minimize their sum of absolute prefix sums. We show several complexity results for this problem that imply some of the mentioned hardness results for wiggle minimization. TU Wien, [email protected] by the Vienna Science and Technology Fund (WWTF) under grant [10.47379/ICT19035] TU Wien, [email protected] by the Vienna Science and Technology Fund (WWTF) under grant [10.47379/ICT19035] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10002950.10003624.10003625.10003627¡/concept_id¿ ¡concept_desc¿Mathematics of computing Permutations and combinations¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10010070¡/concept_id¿ ¡concept_desc¿Theory of computation Theory and algorithms for application domains¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003777.10003779¡/concept_id¿ ¡concept_desc¿Theory of computation Problems, reductions and completeness¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ \crefname algocfAlgorithmAlgorithms ccs Mathematics of computing Permutations and combinations ccs Theory of computation Theory and algorithms for application domains ccs Theory of computation Problems, reductions and completeness keywords Stacked area charts, NP-hardness, Mixed-integer linear programming † † runningtitle: On Minimizing Wiggle in Stacked Area Charts † † runningauthor: A. Dobler and M. Nöllenburg † † copyright: Jane Open Access and Joan R. Public † † supplement: Source code is available online [ 5 ] . † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Figure 1: (a) A stacked area chart of four time series on six time points. The time series are ordered according to \pi from bottom to top. (b) Illustration of the wiggle between time points 4 and 5 on the border between the green and violet time series. For the weighted wiggle, |W_{i,j}| is multiplied by the average of \pi(i)(j) , \pi(i)(j+1) , \pi(i+1)(j) , and \pi(i+1)(j+1) . The total (weighted) wiggle is the sum of all (weighted) wiggle values. Stacked area charts are a widely used method for visualizing numerical time series across discrete time points, such as population data of countries over time or movie revenues over multiple weeks [ 9 , 4 ] . In stacked area charts, the x -dimension depicts time, and the time series are stacked as variable-height strips on top of each other without gaps, such that their heights depict their values (see \cref fig:stackedareacharta). The lowest border of the stacked time series is a straight horizontal line. A primary aesthetic criterion for stacked area charts is wiggle – the aggregated amount of vertical change of the borders between the time series in the visualization ( \cref fig:stackedareachartb). Further, the wiggle is usually weighted by the time series values, resulting in weighted wiggle (for a formal definition refer to \cref section:prelims). For a stacked area chart of a specific dataset, the amount of wiggle solely depends on the vertical ordering of the time series. The task of minimizing wiggle has already been tackled with heuristic methods [ 4 , 13 ] . But despite the popularity of stacked area charts in mainstream visualizations, no work was done with regard to the computational complexity of minimizing wiggle. This paper fills the gap and presents several complexity lower bounds for minimizing wiggle and weighted wiggle. We also compare a state-of-the-art heuristic for minimizing weighted wiggle with a new mixed-integer linear programming formulation on a set of real-world data; the evaluation shows that the heuristic performs well with regard to wiggle minimization and that the mixed-integer program can solve small to medium-size instances exactly. Further, a special case of minimizing wiggle is discussed that results in a fundamentally interesting problem – ordering a set of numbers such that the accumulation of all absolute prefix sums is minimized. Despite its natural problem definition, the problem has not been studied yet. Its relevance comes from its relation to several ordering problems that minimize accumulated cost, such as scheduling problems. Results for this problem are also used to show some hardness results for minimizing wiggles. Related work. The origin of stacked area charts is unclear, as they are a very natural and frequently used visualization for a commonly occurring type of data. The most notable work for popularizing research on stacked area charts is from 2008 by Byron and Wattenberg [ 4 ] , since receiving more than 600 citations. Given the extensive literature on stacked area charts, we focus on studies specifically addressing wiggle minimization and similar aesthetic criteria in related visualizations. Byron and Wattenberg [ 4 ] only deal with data that represent movie revenues. Such data have very specific properties – a movie starts airing, its revenues grow quickly, and then the revenues slowly decrease. Thus, they present a very specific ordering approach that orders the movies by their first screening. They also consider a similar type of visualization, called streamgraphs . The only difference between streamgraphs and stacked area charts is that the lower border of a streamgraph does not have to be a horizontal line, introducing another degree of freedom. Still, wiggle minimization is defined equivalently for streamgraphs. Byron and Wattenberg present a similar ordering procedure for streamgraphs. Furthermore, they consider the task of computing the lower border of visualization given a fixed vertical order of time series. For that task, they show an optimal polynomial time algorithm that minimizes the squared weighted wiggle (each wiggle value is squared instead of taking its absolute value). Greffard and Kuntz [ 7 ] present an approach for weighted squared wiggle minimization in streamgraphs that first defines pairwise dissimilarity values between time series and then applies traveling salesperson approaches. Di Bartolomeo and Hu [ 2 ] present a heuristic and local search algorithm for weighted wiggle minimization in streamgraphs, which also work for stacked area charts. In addition, they show how to, given a fixed order of time series, compute the lower border of the streamgraph that minimizes weighted wiggle. Bu et al. [ 3 ] present an ordering algorithm for streamgraphs that is based on clustering. They also optimize for minimizing what they call sine illusion effect – time series borders mimicking a sine wave. He and Li [ 8 ] present an ordering approach for stacked area charts based on a