EAGER: Geometry and Combinatorics of Intersections and Contacts

EAGER：交叉点和接触点的几何和组合学

• 批准号: 1624382
• 负责人: Stephen Kobourov
• 金额: $ 6万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-05-15 至 2018-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1624382&HistoricalAwards=false
• 关键词: EAGER; Geometry; Combinatorics; Intersections; Contacts

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.

将硬币平放在桌子上并将它们推在一起。 记录硬币对就可以得到“接触图”。作为记录对象之间联系的“图”的简单抽象非常强大：互联网上的计算机、锦标赛括号、社交网络和 PERT 图表都可以被有效地视为图。 具有二维或更多维中接触或相交对象的几何实现的图具有特殊属性（例如，80 或 40 年前就知道可以绘制没有交叉的图可以实现为硬币的接触图。）该项目考虑哪些类型的图可以是 2、3 或更高维度的各种几何对象的接触图或交集图，以及计算机算法如何利用这些图的属性。 该项目得到了美国国家科学基金会计算与通信基础部门和国际科学与工程办公室的支持，为来自德国的洪堡研究员 T. Ueckerdt 提供配套资金，让他与 Kobourov 博士及其学生在伦敦大学进行博士后研究。亚利桑那。