Algorithm Engineering for Geometric Graphs

在我们的RU中，图形直接表现为制图图，或间接表现为几何对偶图、快捷图或三角图。在这个项目中，我们将把这些结构视为几何图形，即嵌入在平面（或表面）上的图形。这些图通常是稀疏的，甚至是平面的，因此允许比一般图更有效的图算法。我们将开发算法工程方法，以实际解决与RU中出现的聚类、聚合和简化问题相关的几何图上的离散优化问题。一个重要的目标是加速和提高几何图上离散（多目标）优化问题的组合和整数线性规划方法的质量。这将通过仔细考虑给定输入数据的图拓扑和（几何）结构来实现，有时与学习方法相结合。对于其中的一些问题，我们将与B1共同开发的新的几何图相似度度量将发挥重要作用。另一个重要因素是精心设计的数据结构，以支持对图形和交互式地图的查询。作为桥梁项目，我们将与B1合作，确保在A1、A2、A3项目中提出的理论概念和算法在测量学项目C1、C2中找到合适的实现。我们的工作计划与所有其他子项目紧密相连。

Within our RU graphs appear directly as cartographic maps or indirectly as their geometric dual graphs, as shortcut graphs or as triangulations. Within this project, we will consider these structures as geometric graphs, i.e. graphs embedded on the plane (or on a surface). These graphs are often sparse, even planar, and thus allow for more efficient graph algorithms than general graphs. We will develop algorithmic engineering approaches for practically solving discrete optimization problems on geometric graphs related to the clustering, aggregation, and simplification problems that occur within our RU. An important goal is to speed up and to improve the quality of combinatorial as well as integer-linear-programming approaches for discrete (multi-objective) optimization problems on geometric graphs. This will be achieved by carefully taking the graph topology and the (geometric) structure of the given input data into account, sometimes in combination with learning approaches. For some of these problems, new similarity measures for geometric graphs, which we will develop jointly with B1, will play an important role. Another important ingredient are carefully engineered data structures to support queries about graphs and interactive maps.As a bridge project, jointly with B1, we will make sure that the theoretical concepts and algorithms suggested in projects A1, A2, and A3 will find a suitable realization in the geodesy projects C1 and C2. Our work program is closely interlinked with all the other subprojects.