Graph Theory and Geometry

本研究项目致力于研究(a)图的交叉数及其与其他图属性的关系，以及(b)几何图的极值问题。图的交叉数通常定义为在平面上绘制图的最小边交叉数或最小边对交叉数。人们普遍认为这两个定义是等价的。然而，没有强有力的证据表明情况会是这样。研究者的目标是澄清这个问题，并对满足某些特殊条件的图的交叉数给出新的估计。一些类似的估计被证明适用于离散几何中的一些经典开放问题，包括上面的边界问题。从下至下依次为单位数(如：由点集确定的不同距离，Erdos和Lovasz的k集问题等，它们也涉及到代数几何中的一些深层次问题。一些现有的交点数的界限在几何图（即直线段绘制的图）理论中有直接的应用，这是本建议的另一个主要主题。研究者计划发展一些关于几何图的一般理论，类似于关于抽象图的丰富而富有成果的极值图论和拉姆齐理论。机器人学和计算机图形学中的许多基本问题都涉及平面上线段排列的深奥数学问题。连接平面上n个点的线段（“边”）系统称为n个顶点的几何图。对于实际应用中出现的几何图问题，传统的图论往往不能给出令人满意的答案。为了解决这些问题，研究者和他的同事们开发了一些结合组合和拓扑思想的新技术。作为副产品，他们获得了一些令人惊讶的结果来估计图（网络）的交叉数，这是一个已知与VLSI布局所需的最小芯片面积密切相关的参数。本研究的目的是利用更多的拓扑工具来更好地理解和改进这些估计。这可能在离散几何和计算几何以及图形绘制的理论和实践中有许多重要的应用。

This research project is devoted to investigating (a) crossing numbers of graphs and their relationships to other graph properties, and(b) extremal problems for geometric graphs.The crossing number of a graph is usually defined as the minimum number of edge crossings or the minimum number of crossing pairs of edges in a drawing of the graph in the plane. These two definitions are widely believed to be equivalent. However, there is no strong evidence that this would be the case. The investigator's goal is to clarify this question and to give new estimates for crossing numbers of graphs satisfying some special conditions. Some similar estimates turned out to be applicable to a number of classical open problems in discrete geometry, including the problem of bounding from above (resp. from below) the number of unit (resp. distinct) distances determined by a point set, the k-set problem of Erdos and Lovasz etc, and they are also related to some deep questions in algebraic geometry. Some existing bounds on crossing numbers have direct applications in the theory of geometric graphs (i.e., graphs drawn by straight-line segments), the other main subject of the present proposal. The investigator plans to develop some general theories for geometric graphs, analogous to the rich and fruitful fields of Extremal Graph Theory and Ramsey Theory for abstract graphs. Many basic problems in robotics and in computer graphics lead to deep mathematical questions about arrangements of segments in the plane. A system of segments (`edges') connecting n points in the plane is called a geometric graph on n vertices. Traditional graph theory is often incapable of providing satisfactory answers to questions on geometric graphs arising in practical applications. To address these problems, the investigator and his colleagues have developed some new techniques combining combinatorial and topological ideas. As a by-product, they obtained some surprising results to estimate the crossing number of a graph (network), a parameter known to be intimately related to the minimum chip area required for its VLSI layout. The aim of the proposed research is to better understand and to improve these estimates by utilizing more involved topological tools. This may have many important applications in discrete and computational geometry and in the theory and practice of graph drawing.