RUI: Geometric Intersection Graphs

The University Corporation, Northridge, Northridge CA

Investigators

Abstract

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.