Solving Crossing Number Problems With Applications

绘制图形是将顶点和边一对一地放置到平面中，使边成为连续的曲线。VLSI理论和计算几何中的许多重要问题都可以归结为图形绘制问题。例如，在VLSI理论中，最小边交叉数问题或交叉数问题已经得到了广泛的研究。此外，离散和计算几何中的一类有趣的问题展示了可以被视为交叉概念的变体、推广和扩展的结构。其中一些问题可以转化为关于团、独立集和图的交图的色数的问题。此外，在许多使用图表表示的科学领域中，自动生成图形是很常见的。这些问题中的大多数都是计算困难的，因此只有关注于解决这些问题的近似算法的设计是有意义的。遗憾的是，许多这类问题的几何性质还没有被很好地理解，需要进一步的研究来研究新的和有效的逼近算法的设计，或者改进和提高现有算法的性能来解决这些问题。理论目标是开发新的结构结果和理论上有效的近似算法，以产生可证明的接近最优解。实验目标是实现这些算法，并在实践中测试和记录它们的有效性。

A drawing of a graph is a one-to-one placement of the vertices and edges into the plane so that the edges become continuous curves. Many important problems in theory of VLSI and computational geometry can be stated as graph drawing problems. For instance, the problem minimizing the number of edge crossings, or the crossing number problem, has been extensively studied in theory of VLSI. Moreover, a class of interesting problems in discrete and computational geometry exhibit structures which can viewed as variations, generalizations and extensions of the notion of crossings. Some of these problems can be reformulated as problems concerning cliques, independent sets and the chromatic numbers of the intersection graphs of drawings. In addition, automatic generation of drawings is customary in many scientific areas in which diagrammatic representations are used.Most of these problems are computationally difficult, and therefore it only makes sense to focus on the design of approximation algorithms for solving them. Unfortunately, geometric properties of many such problems are not well understood, and additional research is needed to investigate the design of new and effective approximation algorithms, or to sharpen and improve the performance of the existing algorithms for solving them.This project is aimed at studying a collection of problems that arise in drawings of graphs in the plane. The theoretical goal is to develop new structural results and theoretically efficient approximation algorithms that can produce provably near optimal solutions. The experimental goal is to implement these algorithms and test and document their effectiveness in practice.