Beyond-planarity: A generalization of the planarity concept in graph drawing

超越平面性：图形绘制中平面性概念的概括

• 批准号: 364468267
• 负责人: Professor Dr. Michael Kaufmann, Ph.D.
• 金额: --
• 依托单位: Fachbereich IV: Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/364468267?language=en
• 关键词: Beyond; planarity; generalization; concept; graph

The research field of graphs beyond planarity has been developed in recent years tremendously; evidence are several workshops and Dagstuhl seminars with this particular topic, as well as a survey book that will be published soon. In the first proposal in 2017, we gave a wide collection of research tasks in various directions. Meanwhile, we contributed in several directions; we summarized this in the progress report. However, we have also identified several new interesting research challenges and directions that we want to follow.1. Classification: We want robust definitions that are also parametrizable (fan-planar -> k-fan-planar, k-gap-planar -> (k,l)-gap-planar). We also want clear hierarchies between different graph classes. We expect to find new classes that complete the hierarchic structure. The classification will also be accompanied by combinatorial and algorithmic analyses on structural properties and parameters (e.g., low degree, girth etc) of the considered classes. 2. Layout: During the first project phase, we observed that the work on layout algorithms for graphs beyond planarity is very limited. The main reason for this is that the known techniques cannot be adopted so easily. Therefore, during the second project phase we will put our main focus on this aspect. For example for the standard approach to compute an appropriate topological embedding, and then a corresponding geometric embedding, both steps are challenging for the case of graphs beyond planarity and provide a considerable portion of risk in the project. To find algorithms which are practically applicable, we plan to provide fast exponential-time algorithms, maybe refined by parametrization, or efficient heuristics that can produce close-to-optimal layouts. It is definitely a far-from-trivial task to find corresponding requirements for more complex classes. Only elementary results are currently known mostly limited to the class of 1-planar graphs.3. Dissemination: By organizing meetings with other groups, we will develop the field further keeping the topic of beyond planarity as a central topic in regular workshops such as GNV in Heiligkreuztal, BWGD in Bertinoro and Dagstuhl. At such workshops, we find new insights by combining forces with people from combinatorial graph theory and computational geometry but also from algorithmic graph theory (e.g., Pach, T\'oth, Hoffmann, Speckmann). In 2016 and 2019, the applicant co-organized two Dagstuhl seminars on beyond planarity. A new edition of this successful Dagstuhl seminar is currently under consideration. As a side note, we further mention that in 2021 our group will be organizing the 29th Symposium of Graph Drawing and Network Visualization in Tübingen, a great honor and appreciation of our work in the field.

超越平面性的图的研究领域近年来得到了巨大的发展； 证据是一些针对这一特定主题的研讨会和 Dagstuhl 研讨会，以及即将出版的一本调查书。在2017年的第一个提案中，我们给出了各个方向的广泛研究任务。同时，我们在几个方面做出了贡献；我们在进度报告中对此进行了总结。然而，我们还确定了一些新的有趣的研究挑战和我们想要遵循的方向。1。分类：我们需要可参数化的稳健定义（fan-planar -> k-fan-planar、k-gap-planar -> (k,l)-gap-planar）。我们还希望不同图类之间有清晰的层次结构。我们期望找到完成层次结构的新类。分类还将伴随着对所考虑类别的结构特性和参数（例如，低度、周长等）的组合和算法分析。 2.布局：在项目的第一个阶段，我们观察到超越平面性的图形布局算法的工作非常有限。其主要原因是已知的技术不能那么容易地采用。因此，在第二个项目阶段我们将主要关注这方面。例如，对于计算适当的拓扑嵌入，然后计算相应的几何嵌入的标准方法，这两个步骤对于超出平面性的图的情况都具有挑战性，并且在项目中提供了相当大的风险。 为了找到实际适用的算法，我们计划提供快速指数时间算法，可以通过参数化或可以产生接近最佳布局的有效启发式进行改进。为更复杂的类找到相应的要求绝对是一项艰巨的任务。 目前只知道基本的结果，大多局限于一平面图类。3．传播：通过与其他团体组织会议，我们将进一步发展该领域，将超越平面性主题作为定期研讨会的中心主题，例如 Heiligkreuztal 的 GNV、Bertinoro 和 Dagstuhl 的 BWGD。在此类研讨会上，我们通过与来自组合图论和计算几何以及算法图论（例如 Pach、T'oth、Hoffmann、Speckmann）的人们的力量相结合，找到了新的见解。申请人于2016年和2019年联合举办了两场关于超平面性的Dagstuhl研讨会。目前正在考虑举办这一成功的 Dagstuhl 研讨会的新版本。作为旁注，我们进一步提到，2021 年我们小组将在蒂宾根组织第 29 届图形绘制和网络可视化研讨会，这是对我们在该领域工作的极大荣誉和赞赏。