Research
Readable Graph Drawings
Graphs are not only a common tool for modeling and solving problems in computer science, but are also often used for visualizing data. Concrete drawings of graphs are understandable also for non-experts because the representation of a link is intuitive. Methods for graph drawing are, moreover, also useable for the visualization of real-world networks such as metro networks. We develop and investigate algorithms for creating readable drawings of graphs.
Algorithms for Geographic Information Systems
A Geographic Information System (GIS) allows users to acquire, administrate, analyze, and visualize geographic information. In this context, algorithmic problems arise, which often are of geometric nature. For instance, building footprints have to be generated automatically from raw data (e.g., from 3-dimensional point clouds acquired by laser scanning). Generally, the level of detail and the level of abstraction of a geospatial dataset have to fit a given application – urban planning, for example, needs more detailed data than climate modelling. Therefore, algorithms for map generalization are needed, which adapt a geospatial dataset to a lower level or detail (or higher level of abstraction). In particular, generalization is used in cartographic visualization to generate small-scale maps from large-scale maps.
Competitive Location Problems
We investigate a class of location problems where two competing providers place their facilities sequentially and users can decide between the competitors. We assume that both competitors act non-cooperatively and aim at maximizing their own benefit. We investigate the complexity and approximability of such problems on graphs, in particular on simple graph classes such as trees and paths. We also develop fast algorithms for single competitive location problems where each provider places one single facilty.
Complexity and Automata
We study properties of complete sets of complexity classes, e.g. the redundancy of NP-complete sets. It is conjectured that all NP-complete sets are highly redundant, but this cannot be shown in general. Therefore, we search for weaker redundancy statements that can be verified for all NP-complete sets.
