Engineering Linear Ordering Algorithms for Optimizing Data Visualizations

Optimizing linear orderings of objects is a fundamental problem for many types of data visualizations ranging from graph layouts over geospatial data to abstract sets and sequences or time-series data. Yet a systematic investigation of algorithms for solving novel constrained and application-specific ordering problems that go beyond well-studied and NP-hard classic ordering problems is missing. Practical work in visualization often resorts to heuristics without rigorous performance and quality guarantees for solving these algorithmic problems. In this project we will take an algorithmic perspective on several different ordering problems in data visualization. In the algorithm engineering sense we want to cross the gap between fundamental theory and practical applications and aim to bring the benefit of rigorous formal methods into practically relevant implementations and at the same time define new algorithmic challenges inspired by recent visualization problems. On the one hand, we will investigate the complexity of new problem settings with special input configurations, structural constraints on feasible orderings, and dependencies between multiple objects and orderings. On the other hand, we will design and implement new and sufficiently scalable algorithms with formally proven performance guarantees to compute optimal and approximate solutions. We thoroughly evaluate the improvements over existing state-of-the-art heuristics in computational experiments and user studies.