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 (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 Doctoral Program "Discrete Mathematics" offers an advanced PhD training and research program which is run jointly by

• Graz University of Technology (TU Graz),
• University of Graz (KFU Graz), and
• University of Leoben (MU Leoben).

It is funded by the Austrian Science Fund (FWF) and the three supporting universities.

Range of topics

The range of topics in Discrete Mathematics comprises

• Commutative and noncommutative Algebra
• Number Theory
• Additive Combinatorics
• Discrete Dynamics and Fractals
• Graph Theory
• Combinatorial Group Theory
• Discrete Stochastics
• Combinatorial Optimisation
• Discrete and Computational Geometry
• Analysis of Algorithms

You can find the individual projects here and the open positions here.

Erdős-Szekeres type questions on convex subsets of point sets are among the most classical and long-standing problems in the area of combinatorial mathematics and discrete geometry. Their origins go back to 1933 when Eszter Klein asked the following question: Is it true that for any integer k there is a smallest integer g(k) such that any set of at least g(k) points in the plane contains a convex subset of cardinality k? Prominent variations of the original question from Eszter Klein are to require empty convex sets and to ask about the number of convex empty subsets of a certain size.
For many questions in discrete geometry the goal is to obtain extremal configurations, that is, structures attaining the minimum or maximum number of the considered geometric objects. For Erdős-Szekeres type questions it is well known that sets in convex position and Horton sets often show this extreme behavior. Informally, Horton sets are very anti-convex, and thus it is natural to study the behavior of sets of different degrees of convexity. One proposed approach in this respect is to investigate the size and the number of convex subsets in k-convex point sets.
In this project we investigate questions of the above flavor, for example the search for convex holes in k-convex point sets and the number of general (that is, not necessarily convex) k-holes in point sets.

This CRP focuses on combinatorial properties of discrete sets of points and other simple geometric objects primarily in the plane. In general, geometric graphs are a central topic in discrete and computational geometry, and many important questions in mathematics and computer science can be formulated as problems on geometric graphs. In the current context, several families of geometric graphs, such as proximity and skeletal structures, constitute useful abstractions for the study of combinatorial properties of the point sets on which they are defined. For arrangements of other objects, such as lines or convex sets, their combinatorial properties are usually also described via an underlying graph structure.