Grant: Alliance Grants

Graphs represent pairwise relationships (edges) between objects (vertices) and appear in various guises across all branches of science and humanities: flow charts, molecule diagrams, entity-relationship models, circuits, communication networks, social networks, road networks, neural networks, and phylogenetic trees are just a few examples of other names given to graphs. In a recent breakthrough, the team of applicants and international collaborators proved the Product Structure Theorem for Planar Graphs. This result shows that any planar graph is the product of two much simpler graphs, a tree-like graph and a path. This result makes it possible to use a wide variety of tools developed for tree-like graphs to solve problems on planar graphs. Within weeks, this discovery led to the resolution of several decades-old research problems on planar graphs and has since led to the field that is now dubbed "graph product structure theory". The project has three main research goals: 1. New applications of graph product structure theory to graph theoretic problems. 2. Product structure results for beyond-planar graph classes. 3. Algorithmic aspects of graph product theory. The funds from this project will be used to support the project's training goals: 1. To increase the number of highly-qualified personnel trained in the use of tools and techniques provided by graph product structure theory. 2. To create highly-qualified personnel that are well-rounded experts in the development and application of graph product structure theory and the techniques that support it.