权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Algorithmic Methods for Crossing Numbers and other Non-planarity Measures

交叉数和其他非平面性测量的算法方法

基本信息

批准号：
285614448
负责人：
Professor Dr. Markus Chimani
金额：
--
依托单位：
Arbeitsgruppe Theoretische Informatik
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2015
资助国家：
德国
起止时间：
2014-12-31 至 2021-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/285614448?language=en
关键词：
Algorithmic Methods Crossing Numbers other

项目摘要

The crossing number of a graph is the smallest number of pairwise edge crossings that are necessary when drawing the graph in the plane. The problem to determine the crossing number of a graph is a classical problem in topological graph theory; it constitutes the probably best-known concept among a set of several different non-planarity measures. The study of crossing numbers is roughly 70 years old, and started out mostly in the realm of graph theory. Algorithmically, there was only slow progress in the early years. However, especially the last 10-20 years brought us several algorithmic advancements, to better understand the NP-complete crossing number problem. Nonetheless, several fundamental questions, for instance the problem's approximability, are still open. On the one hand, the aim of this project is to develop new algorithmic methods to solve the crossing number approximatively or exactly. We thereby combine theoretical research with the concepts of Algorithm Engineering, to devise schemes that are also applicable for real-world applications. On the other hand, we also consider other non-planarity measures. We want to use our crossing number experience to develop new algorithmic approaches for those. We may explicitly mention the (also NP-hard) maximum planar subgraph problem, as well as its relatives maximum induced planar subgraph/vertex deletion number and vertex splitting number. Those problems arise frequently in practice, but constitute demanding challenges for exact and approximative solution strategies.

图的交叉数是在平面上绘制图时所需的成对边交叉的最小数目。确定图的交叉数的问题是拓扑图论中的一个经典问题;它构成了一组几种不同的非平面性度量中最著名的概念。交叉数的研究大约有70年的历史，并且主要是在图论领域开始的。从数学上讲，最初几年进展缓慢。然而，特别是过去10-20年给我们带来了一些算法的进步，以更好地理解NP完全交叉数问题。尽管如此，一些基本问题，例如问题的可近似性，仍然是开放的。一方面，本项目的目的是开发新的算法方法来近似或精确地求解交叉数。因此，我们结合联合收割机的理论研究与算法工程的概念，设计方案，也适用于现实世界的应用。另一方面，我们还考虑了其他非平面性措施。我们希望利用我们的交叉数经验来开发新的算法方法。我们可以明确地提到（也是NP困难的）最大平面子图问题，以及它的相关最大诱导平面子图/顶点删除数和顶点分裂数。这些问题在实践中经常出现，但对精确和近似的解决策略构成了严峻的挑战。