David Wood: Universal Graph Product Structures

Abstract. This talk will survey recent results that describe graphs as subgraphs of products of simpler graphs. The starting point is the following theorem: every planar graph is a subgraph of the strong product of some treewidth 7 graph and a path. This result has been the key to solving several open problems, for example, regarding the queue-number and nonrepetitive chromatic number of planar graphs. The result generalises to provide a universal graph for planar graphs. In particular, if $T^{}$ is the universal treewidth 7 graph (which is explicitly defined), then every countable planar graph is a subgraph of the strong product of $T^{}$ and the infinite 1-way path. This result generalises in various ways for many sparse graph classes: graphs embeddable on a fixed surface, graphs excluding a fixed minor, map graphs, etc. For example, we prove that for every fixed graph $X$, there is an explicitly defined countable graph $G$ that contains every countable $X$-minor-free graph as a subgraph, and $G$ has several desirable properties such as every $n$-vertex subgraph of $G$ has a $O\left(\sqrt{n}\right)$-separator. On the other hand, as a lower bound we strengthen a theorem of Pach (1981) by showing that if a countable graph $G$ contains every countable planar graph, then $G$ must contain an infinite complete graph as a minor.