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年来人们已经知道，可以在没有交叉的情况下绘制的图形可以实现为硬币的接触图形。)这个项目考虑了什么类型的图可以是二维、三维或更高维的各种几何对象的接触图或交叉图，以及这些图的性质如何被计算机算法利用。该项目由NSF计算和通信基金会部门和国际科学与工程办公室支持，为来自德国的洪堡研究员T.Ueckerdt提供等额资金，用于在亚利桑那大学与Kobourov博士和他的学生一起度过博士后一年。