Algorithmic Methods for Crossing Numbers and other Non-planarity Measures

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

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.