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.