Solving Crossing Number Problems With Applications

使用应用程序解决交叉号码问题

• 批准号: 9988525
• 负责人: Farhad Shahrokhi
• 金额: $ 16.93万
• 依托单位: University of North Texas
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-08-01 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9988525&HistoricalAwards=false
• 关键词: Solving; Crossing; Number; Problems; Applications

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.

图的绘制是将顶点和边一对一地放置到平面中，使得边成为连续的曲线。 在超大规模集成电路理论和计算几何中的许多重要问题都可以归结为作图问题。 例如，边交叉数最小化问题，或交叉数问题，已经在VLSI理论中被广泛研究。 此外，在离散几何和计算几何中，一类有趣的问题表现出的结构可以被看作是交叉概念的变化、推广和扩展。 这些问题中的一些可以转化为关于图的交图的团、独立集和色数的问题。 此外，自动生成图形在许多使用图形表示的科学领域中是很常见的。这些问题中的大多数在计算上是困难的，因此只关注于设计近似算法来解决它们才有意义。 不幸的是，许多这样的问题的几何属性没有得到很好的理解，需要进行更多的研究，以调查新的和有效的近似算法的设计，或锐化和改善现有的算法的性能，以解决them.This项目的目的是研究一系列的问题，出现在图纸中的图形在平面上。 理论目标是开发新的结构结果和理论上有效的近似算法，可以产生可证明的接近最优解。 实验的目标是实现这些算法，并测试和记录其在实践中的有效性。