Algorithms for schematic representations : on the complexity of computing schematic representations of transit maps, graphs and geometric objects

Abstract

Schematic representations display data in a way that highlights certain properties at the cost of being less accurate for other aspects of the data. They are an ubiquitous tool to explore and understand data as well as making it more immediately accessible for specific purposes. Schematic representations (or schematizations) are commonly used to display geospatial data with the goal of reducing complexity and thereby making the map more readily readable. This can be done by simplifying borders between regions for different zoom levels and omitting detail, which would not be visible (e.g. in digital versions of political maps), by orienting all straight lines of a map along a very restricted set of predefined orientations (e.g. in transit maps like metro networks) or by distorting the shape of elements on a map into simple geometric primitives to facilitate easy identification and comparability between objects (e.g. in some cartograms), to name just a few. The creation of a schematic representation (geospatial or otherwise) is often a time-intensive task for a designer and small changes, might require large scale redesigns. There has been rising interest in supporting or completely automating parts of the design process with suitable algorithmic solutions. From a practical perspective, any such algorithmic support enables a designer to explore a larger set of possible designs, without wasting a large amount of manual work. However from a theoretical perspective it turn out that in many common design task there are difficult or intractable problems hidden. Therefore automated approaches (in particular when aiming to provide a more or less finished high-quality output) have to tackle these task by employing the appropriate tools. This might take the form of encoding the design problem as a mathematical formulation, for which already existing and highly optimized solvers can be used. Or one can aim to identify, which part of a problem is the source for the intractability by restricting input instances or allowing the runtime to only scale problematically with certain parameters of the input, which we can expect to be small in a real world setting. In this thesis we aim to approach various schematic representation problems from tow sides. On one hand we investigate the complexity of solving, by showing that a problem formulation is NP-hard or NP-complete using polynomial time reductions. And on the other hand, we provide mathematical constraint programming formulations, heuristics, parameterized XP- or FPT-algorithms or polynomial time algorithms for restricted input classes, which allow us to find solutions to (some) of these problems, in spite of their theoretical hardness.