Arrangements and Drawings (ArrDra)

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 Arrangements and Drawings 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 from the following four focus areas: (A) Arrangements of lines and pseudolines, (B) Drawings of graphs, (C) Structure of intersection, and (D) 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 (TU Berlin, FU Berlin, ETH Zürich, and TU Graz) 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.

The central topic of the collaborative trilateral D-A-CH project "Arrangements and Drawings" are arrangements of geometric objects and drawings of graphs, two fundamental concepts at the core of discrete and computational geometry. The project consisted of four subprojects led by Stefan Felsner (TU Berlin), Wolfgang Mulzer (FU Berlin), Michael Hoffmann (ETH Zürich), and Birgit Vogtenhuber (TU Graz). We focussed on combinatorial, existential, and complexity-theoretic questions, with the ambitious goal of relevantly furthering the knowledge about the studied structures and especially also attacking long-standing open problems. We composed a list of challenging problems from four focus areas, namely, (A) Arrangements, (B) Drawings of graphs, (C) Structure of intersection, and (D) Planar and near-planar structures. Instead of assigning each of them to one subproject, we planned to conduct intensively collaborative research between the groups and with external partners. We are happy and proud to report that this plan has been accomplished. Many proposed problems have been successfully investigated. One example are Erds-Szekeres type questions. Around 1933, Klein asked, whether for every integer k there is an integer g(k) such that every set of g(k) points in general position in the plane contains a convex polygon with k vertices. Initiated by this question and its positive answer by Erds and Szekeres, a whole class of related problems about the existence and number of polygons in point sets evolved and became famous as Erds-Szekeres type questions. We have published several results on such questions. Most notably, we have shown the first superlinear lower bound on the number of pentagons without interior points, by this confirming an over 30 year old conjecture. A second example is the problem of partitioning a drawing of a graph with straight-line edges - which might have many crossings - into as few as possible plane subdrawings (that is, drawings without crossings). The according computational problem has been posed as the Computational Geometry Challenge (CG:SHOP 2022) in the course of the 38th International Symposium on Computational Geometry (SoCG 2022), the flagship conference of the field. For complete graphs on 2n vertices, it had long been conjectured that they can always be partitioned into n plane spanning trees. In collaboration between three groups of the project, we disprove this conjecture and show that not even a partition into n arbitrary plane subdrawings is always possible. Altogether, the Austrian team has collaborated on 37 articles in international journals and peer-reviewed competitive conferences. One of them has received a best paper award, and six have have been selected for publication as special issue of a conference. The research made possible by the project has not only been fruitful but also exciting and joyful, and we plan to continue this collaboration in the future.