EAGER: Geometry and Combinatorics of Intersections and Contacts

University Of Arizona, Tucson AZ

Investigators

Abstract

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.