This is the webpage of a D-A-CH collaborative project, funded by DFG (Deutsche Forschungsgemeinschaft), FWF (Austrian Science Fund), and SNSF (Swiss National Science Foundation). Click here to get to the webpage of the Swiss team of the ArrDra project.

Project Description

Arrangements of geometric objects and drawings of graphs lie at the core of modern Discrete and Computational Geometry. They serve as a flexible tool in applications in both mathematics and computer science, since many important problems that involve geometric information may be modeled as problems on arrangements or graphs. Therefore, the study of these structures and a better understanding of their properties impacts a wide variety of problem domains.

This DACH project connects groups that have already cooperated successfully in the European collaborative research programme EuroGIGA. In this follow-up project, we plan to investigate the relationships between different types of drawings and arrangements, as well as their abstract representations and their algorithmic properties. We have composed a list of challenging problems ranging from Erdős-Szekeres type questions via questions about the computational power of sidedness predicates to questions about flip graphs. The backbone of the project is structured into four focus areas:

  • Arrangements of lines and pseudolines,
  • Drawings of graphs,
  • Structure of intersection, and
  • Planar and near-planar structures.

The goal of this project is to gain insights in order to broaden our understanding of these areas and to jointly attack some of their long-standing open questions. These questions are notoriously difficult though important, so that even partial solutions are expected to have impact. Each of the four sites of the DACH project will concentrate efforts on a subset of the focus areas such that research in each of these areas will be conducted in at least two of the four sites.