EAGER: Geometry and Combinatorics of Intersections and Contacts

把硬币平放在桌子上，然后把它们推到一起。 记录这些成对的硬币就可以得到一个“接触图”。简单抽象的“图”作为记录对象之间的连接是惊人的强大：互联网上的计算机，锦标赛括号，社交网络和PERT图表都被有效地视为图。 在两个或更多维度上具有接触或相交对象的几何实现的图具有特殊性质（例如，80年或40年前就已经知道，可以画出没有交叉的图可以实现为硬币的接触图）。 该项目考虑什么类型的图可以是2维、3维或更高维的各种几何对象的接触图或相交图，以及如何通过计算机算法利用这些图的属性。 该项目由美国国家科学基金会计算与通信基金会分部和国际科学与工程办公室支持，并为来自德国的洪堡研究员T。Ueckerdt博士将在亚利桑那大学与Kobourov博士和他的学生一起度过博士后的一年。

Put coins flat on a table and push them together. Recording the pairs of coins gives a "contact graph." The simple abstraction of a "graph" as recording connections between objects is surprisingly powerful: computers on the internet, tournament brackets, social networks, and PERT charts are all usefully viewed as graphs. Graphs that have geometric realizations as contacting or intersecting objects in two or more dimensions have special properties (e.g. it has been known for 80 or 40 years that graphs that can be drawn with no crossings can be realized as contact graphs of coins.) This project considers what types of graphs can be contact graphs or intersections graphs of various geometric objects in 2, 3 or higher dimensions, and how properties of these graphs can be exploited by computer algorithms. This project, supported by NSF Computing and Communication Foundations division and the Office of International Science and Engineering, provides matching funds for a Humboldt fellow from Germany, T. Ueckerdt, to spend a postdoctoral year working with Dr. Kobourov and his students at U of Arizona.