Engineering Linear Ordering Algorithms for Optimizing Data Visualizations

The digital transformation of our society and the ubiquitous use of digital technology in our everyday life bring many opportunities, but also risks and challenges. Smart watches and cell phones track our health data and movement patterns, while interactions in social media and electronic shopping create traces of our contacts and purchase patterns. These and many more data are collected day by day and lead to massive amounts of information that need to be stored, processed, and analyzed. Our research project focused on data visualization, which aims to represent data clearly and understandably so that people can explore, engage with, and make decisions based on their findings. Specifically, we investigated how to optimally arrange and order objects in data visualizations to improve various quality criteria, such as minimizing clutter and enhancing readability. Examples of such ordering problems in data visualization include arranging nodes in linear or circular network diagrams to reduce edge crossings, optimally placing external callout labels for feature points in graphical illustrations, or creating storyline charts that depict character interactions over time in a movie or novel. Our approach relies on rigorous algorithmic tools and mathematical proofs to develop fast algorithms with guaranteed solution quality, setting us apart from commonly used heuristics that lack formal guarantees. Throughout the duration of the project, our team tackled a variety of challenging research questions. We created algorithmic models for popular types of data visualizations, developed new optimization algorithms, and analyzed their performance through mathematical proofs. To demonstrate that the new methods provide not only theoretical advantages, but also improve the visualizations in practice, we implemented and evaluated them against existing state-of-the-art solutions through simulations and user experiments. Some highlights of our research, published in over 35 peer-reviewed articles presented at prestigious international conferences and often implemented as open source web prototypes, include new methods to visualize complex datasets such as musical genres and artists or scientists and their co-authored publications. These visualizations resemble abstract metro maps, compact linear diagrams, or intertwined storyline plots. Other results focused on the optimal arrangement of variable-width streams showing the evolution of hierarchies over time, the minimization of block crossings in evolutionary tree diagrams, and an optimization framework for radial network diagrams. In summary, our project shows that a rigorous approach to optimizing data visualizations can lead to cleaner and more readable charts. This promises to make data exploration more engaging and enjoyable, ultimately supporting data literacy in our society.