Grant: Discovery Grants Program - Individual

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. For many reasons, such as cost, complexity, and geometric constraints, graphs that arise in applications are often sparse; the number of edges in the graph is not more than a constant times the number of vertices.The classic example of sparse graphs are planar graphs whose vertices can be drawn as points in the plane and whose edges can be drawn as non-crossing curves joining their endpoints. Planar graphs arise naturally from a physical representation of some graph (e.g., a road network, a circuit, or a map) on a 2-dimensional surface (e.g., the surface of the earth, a printed circuit board, or a piece of paper) and have been the subject of intense study for nearly 300 years. The proposed research is on structural decompositions of sparse graphs and applications of these decompositions to algorithmic and combinatorial problems. The applicant's recent Product Structure Theorem and its generalizations have led to the resolution of several longstanding open problems on planar graphs and more general sparse graph familes. The main thrust of this research is to extend such product structure decompositions and unify them with more classic graph decompositions such as the Graph Minor Structure Theorem of Robertson and Seymour.  This work proceeds in four directions: 1. Unifications of the Graph Minor Structure and Product Structure Theorems. 2. Algorithms for Product Structured Graph Families. 3. New Applications of Product Structure. 4. Product Structure Decompositions for New Graph Classes. This fundamental research has the potential to impact any branch of the sciences and humanities in which sparse graphs appear.