Algorithm Engineering for Geometric Graphs

点击翻译按钮获取中文摘要

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.