Arrangements and Drawings

几何对象的排列和图形的绘制是现代离散几何和计算几何的核心。它们在数学和计算机科学的应用中都是一种灵活的工具，因为许多涉及几何信息的重要问题可以被建模为关于排列或图的问题。因此，对这些结构的研究和对其性质的更好理解影响到广泛的问题领域。DACH项目将已经在欧洲合作研究计划EuroGIGA中成功合作的小组联系起来。在这个后续项目中，我们计划调查不同类型的图形和排列之间的关系，以及它们的抽象表示和它们的算法性质。我们已经列出了一系列具有挑战性的问题，从ErdöS-Szekeres类型的问题到关于侧性谓词的计算能力的问题，再到关于翻转图的问题。该项目的主干分为四个重点领域。(A)线条及伪线的安排。(B)图表的绘制。(C)交叉口的结构。(D)平面和近平面结构。该项目的目标是获得洞察力，以扩大我们对这些领域的了解，并共同解决它们的一些长期悬而未决的问题。这些问题虽然重要，但难度却是出了名的，因此，即使是部分解决方案也有望产生影响。DACH项目的四个地点中的每一个都将集中精力在重点领域的一个子集上努力，以便这些领域中的每个领域的研究将在四个地点中的至少两个地点进行。

Arrangements of geometric objects and drawings of graphs lie at the core ofmodern Discrete and Computational Geometry. They serve as a flexible tool inapplications in both mathematics and computer science, since many importantproblems that involve geometric information may be modeled as problems onarrangements or graphs. Therefore, the study of these structures and a betterunderstanding of their properties impacts a wide variety of problem domains.This DACH project connects groups that have already cooperated successfully inthe European collaborative research programme EuroGIGA. In this follow-upproject, we plan to investigate the relationships between different types ofdrawings and arrangements, as well as their abstract representations and theiralgorithmic properties. We have composed a list of challenging problems rangingfrom Erdös-Szekeres type questions via questions about the computational powerof sidedness predicates to questions about flip graphs. The backbone of theproject is structured into four focus areas. (A) Arrangements of lines and pseudolines. (B) Drawings of graphs. (C) Structure of intersection. (D) Planar and near-planar structures.The goal of this project is to gain insights in order to broaden ourunderstanding of these areas and to jointly attack some of their long-standingopen questions. These questions are notoriously difficult though important, sothat even partial solutions are expected to have impact. Each of the four sitesof the DACH project will concentrate efforts on a subset of the focus areassuch that research in each of these areas will be conducted in at least two ofthe four sites.