Abstract

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.