Algorithmic Aspects of Ordering Problems in Information Visualization

Abstract

Information visualization plays a central role in understanding and interacting with data by uncovering patterns, trends, and anomalies. The effectiveness of a visualization critically depends on its layout quality, often governed by one or morewell-defined quality criteria. Optimizing visualizations to meet these criteria often leads to challenging computational problems, many of which are NP-hard. Despite this, the visualization literature frequently relies on standard heuristics without provable guarantees, limiting both the rigor and quality of visual outcomes. This thesis addresses this gap by developing provably efficient algorithms for optimizing visualizations with respect to formal quality measures, with a particular focus on problems where these measures depend on orderings or permutations of visual data elements. The work combines algorithm design, complexity theory, and empirical evaluationto rigorously analyze and solve layout optimization problems across several types of visualizations. The thesis is structured into three parts. Part I investigates set visualizations, including linear diagrams and metro-map-style point-line incidence diagrams. We study layout problems where the goal is to order elements and sets to minimize visual complexity metrics in linear diagrams. We provide computational lower bounds and give exact and heuristic algorithms. Furthermore, we investigate geometric representations of set systems using straightlines and show that even basic variants of these problems are computationally intractable. Part II considers crossing minimization in visualizations where entities evolve over time or are grouped hierarchically, including temporal treemaps, storyline visualizations, and tanglegrams. We define theoretical models for counting and minimizing crossings in temporal treemaps, simplify prior ILP approaches for storylines, and introduce block crossing minimization in tanglegrams, providing complexity results and efficient algorithms. Part III addresses wiggle minimization instacked area charts, where the vertical order of bands affects the readability of the visualization. We prove several computational lower bounds, and provide an exact algorithm that we empirically compare against a state-of-the-art heuristic. Throughout the thesis, we apply tools from algorithm design – including parameterized complexity, integer programming, and approximation algorithms – to derive both theoretical insights and practically useful solutions. In doing so, this thesis contributes to a more rigorous algorithmic foundation for information visualization, particularly in contexts where visual quality depends on the ordering of visual dataelements.