Graph Product Structure Theory (21w5235)


(Carleton University)

(University of Ottawa)

(McGill University)

David Wood (Monash University)


The Banff International Research Station will host the "Graph Product Structure Theory" workshop in Banff from November 21 to November 26, 2021.

Graphs are the standard mathematical model of many real-world entities: computer networks, road and highway networks, drainage systems, river networks, electrical networks, and so on. In some cases, these highly-complicated graphs are contained in the product of two or more much simpler graphs. In a recent breakthrough, it was shown that this is the case for planar or near-planar graphs like those that model river, road, and highway networks; any such graph is contained in the product of a simple tree-like graph and a path. This product structure gives deep insight into these graphs and their properties, allowing a host of mathematical and algorithmic tools to be applied to these graphs. The goal of this workshop is to continue the search for product structure in more general classes of graphs as well as to find new methods to exploit such product structure mathematically and algorithmically, when it is present.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).