RUI: Geometric Intersection Graphs

该项目设想了两个主要目标：首先，它研究图形的几何表示理论，建立在广泛的数学方法的基础上，并将结果整合到新技术中。其次，它培养下一代学生从事数学、科学和工程方面的职业，重点是在离散数学方面打下坚实的基础，并培养有效处理几何对象的数学技能。可视化复杂系统和大型数据集已经成为常规，包括低维虚拟对象的用户友好处理。在这种情况下设计高效的计算机工具是一项具有挑战性的任务，它要求对几何对象及其之间的关系的表示方式有透彻的理解，以及熟悉这些数学工具的功能和局限性的高素质开发人员和科学家。在空间中表示图受到拓扑、度量和代数性质的约束。拓扑约束通常被曲线或曲面相交图中不可避免的模式所捕获，并且与组合几何中的ramsey型结果密切相关。公制约束对应于可以同时实现的距离、坡度、角度和面积的模式。当边缘用代数曲线（包括直线）表示时，代数约束起着重要的作用。该项目将研究几何对象的相交模式，其中相交关系由无向图表示，并且还将研究几何图、拓扑图、超图或简单复合体嵌入低维欧几里得空间所产生的相交。相关的枚举问题也将被考虑，其中度量和拓扑约束与经典组合问题相结合产生了新的挑战。基本几何对象（如点、线段、线和二次线）的实现空间的定量边界在制图、计算机科学、优化和实体建模中都有应用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project envisions two main objectives: First, it studies the theory of geometric representations of graphs, building on a broad array of mathematical methods, and integrating the results into new technology. Second, it trains the next generation of students for careers in mathematics, sciences, and engineering, focusing on solid foundations in discrete mathematics, and developing mathematical skills for handling geometric objects efficiently. Visualizing complex systems and large data sets has become routine, including user-friendly handling of virtual objects in low dimensions. Designing efficient computer tools in this context is a challenging task, it calls for a thorough understanding of how geometric objects and relations between them are represented, as well as highly qualified developers and scientists who are familiar with the capabilities and limitations of these mathematical tools.Representing graphs in space is constrained by topological, metric, and algebraic properties. Topological constraints are typically captured by unavoidable patterns in the intersection graph of curves or surfaces, and is closely related to Ramsey-type results in combinatorial geometry. Metric constraints correspond to patterns in distances, slopes, angles, and areas that can be realized simultaneously. Algebraic constraints play an important role when edges are represented by algebraic curves (including straight lines). This project will study the intersection patterns of geometric objects, where the intersection relation is represented by an undirected graph, and it will also examine the intersections created by embeddings of geometric graphs, topological graphs, hypergraphs, or simplicial complexes into Euclidean spaces of low dimensions. Related enumerative problems will be considered, as well, where metric and topological constraints combined with classical combinatorial problems yield new challenges. Quantitative bounds for the realization spaces of basic geometric objects (such as points, line segments, lines, and quadrics) have applications in cartography, computer science, optimization, and solid modelling.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.