Product Structure of Graphs

• Applicant: Privatdozent Dr. Torsten Ueckerdt
• Subject Area: Theoretical Computer Science
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 532213793

The product structure theorem for planar graphs is a way to express planar graphs in terms of graphs with a simpler structure, in a way that proves useful for structural and algorithmic applications. We together with our coauthors proved this theorem recently, building on pioneering works by Pilipczuk and Siebertz. It states that every planar graph is a subgraph of the strong product of a graph of treewidth 8 and a path. The product structure theorem for planar graphs already found a number of important applications in combinatorics and theoretical computer science in a very short time. It is reasonable to expect that more will be found in the near future. This new tool might indeed be the key to make progress on a number of open problems related to planar graphs. In this proposal, we list some directions which we believe have potential in this respect. Besides hunting for new applications, we believe it is worth trying to improve and develop the theory further. First, the current bounds are most likely not tight, so there is a room for improvement. Second, it would be very interesting to identify new graph classes of interest that satisfy some form of a product structure theorem. Right now, besides planar graphs, only a handful of examples are known. Last but not least, we would like to use the synergy of the three PIs working together, and their respective teams, to have a go at tackling some long standing challenges in structural graph theory. Our focus here will be on obtaining the best possible upper bound in the famous grid minor theorem of Robertson and Seymour, one of the corner stones of graph minor theory with countless applications. This is without doubt an ambitious (and risky) objective.

• DFG Programme: Research Grants
• International Connection: Belgium, Poland
• Partner Organisation: Fonds National de la Recherche Scientifique - FNRS; Narodowe Centrum Nauki (NCN)
• Cooperation Partners: Professor Dr. Gwenaël Joret, Ph.D.; Professor Dr. Piotr Micek, Ph.D.