Schedule for: 21w5235 - Graph Product Structure Theory

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

I will prove the planar graph product structure theorem, which states that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. This is joint work with Dujmovi’c, Joret, Micek, Morin & Wood [2020] and with Wood & Yi [2021].

A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the second half. One of the first applications of the product structure theorem was to show that planar graphs have nonrepetitive colourings with a bounded number of colours, solving a problem raised by Alon, Grytczuk, Haluszczak and Riordan in 2002. I will explain the ideas of the proof and show how to extend the result to classes of graphs that are closed under taking topological minors. This is joint work with V. Dujmović, G. Joret, B. Walczak, and D.R. Wood.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath et al.\ from 1992. The key to the proof is the Planar Graph Product Structure Theorem: Every planar graph is a subgraph of the strong product of some treewidth 8 graph and some path. We generalise the first result to show that every proper minor-closed class has bounded queue-number. This is joint work with Vida Dujmovi\'c, Gwena\"el Joret, Piotr Micek, Pat Morin and Torsten Ueckerdt [J. ACM 67.4:22, 2020].

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé, and Watrigant [FOCS 2020] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced-$f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced-bandwidth, which implies and is stronger than bounded twin-width (reduced-maximum-degree). We show that every proper minor-closed class has bounded reduced-bandwidth, which is qualitatively stronger than a result of Bonnet et al.\ for bounded twin-width. In many instances, we also make quantitative improvements using product structures. For example, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced-bandwidth at most $466$ and twin-width at most $583$. Our bounds for graphs of Euler genus $g$ graphs are $O(g)$. Lastly, we show that $d$-powers of graphs in a proper minor-closed class have bounded reduced-bandwidth (irrespective of the degree of the vertices).

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

This talk focuses on the following two problems: (1) What is the minimum number of edges in a graph containing all $n$-vertex planar graphs as subgraphs? The best known bound is $O(n^{3/2})$, due to Babai, Chung, Erdös, Graham, and Spencer (1982). (2) What is the minimum number of *vertices* in a graph containing all $n$-vertex planar graphs as *induced* subgraphs? Here Bonamy, Gavoille, and Pilipczuk (2019) recently established a $O(n^{4/3})$ bound. We show that a bound of $n^{1+o(1)}$ can be achieved for these two problems. Joint work with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin.

A (vertex) $\ell$-ranking is a labelling $\varphi:V(G)\to\mathbb{N}$ of the vertices of a graph $G$ with integer colours so that for any path $u_0,\ldots,u_p$ of length at most $\ell$, $\varphi(u_0)\neq\varphi(u_p)$ or $\varphi(u_0)<\max\{\varphi(u_0),\ldots,\varphi(u_p)\}$. We show that, for any fixed integer $\ell\ge 2$, every $n$-vertex planar graph has an $\ell$-ranking using $O(\log n/\log\log\log n)$ colours and this is tight even when $\ell=2$; for infinitely many values of $n$, there are $n$-vertex planar graphs, for which any 2-ranking requires $\Omega(\log n/\log\log\log n)$ colours. This result also extends to bounded genus graphs. These results rely on product structure theorems showing that every planar (or bounded genus) graph is contained in a graph product of the form $H\boxtimes P\boxtimes K$ where $K$ is a fixed size clique, P is a path, and $H$ is a planar graph of treewidth at most $3$. In particular, it is critical that $H$ is contained in a planar $3$-tree (also known as a simple $3$-tree). In developing this proof we obtain optimal bounds on the number of colours needed for $\ell$-ranking graphs of treewidth $t$ and graphs of simple treewidth $t$. These upper bounds are constructive and give $O(n\log n)$-time algorithms. Additional results that come from our techniques include new sublogarithmic upper bounds on the number of colours needed for $\ell$-rankings of any graph with product structure, including apex minor-free graphs and $k$-planar graphs.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

The Planar Graph Product Structure Theorem says that planar graphs are subgraphs of the strong product of a bounded treewidth graph and a path, which is to say they have bounded row treewidth. This talk explores similar theorems for minor-closed classes that are more general than planar graphs. First, I show that graphs of bounded Euler genus have bounded row treewidth. More generally, a minor-closed class has bounded row treewidth if and only if some apex graph is not in the class. I then show that graphs with bounded degree in any minor-closed class have bounded row treewidth. Finally, I present the Graph Minor Product Structure Theorem, which says that graphs in any minor-closed class have a tree-decomposition in which each torso is a subgraph of $(H\boxtimes P)+K_a$ where $H$ has bounded treewidth, $P$ is a path, and $a$ is bounded. This is joint work with Dujmović, Joret, Micek, Morin and Ueckerdt [J. ACM 2020] and Dujmović, Esperet, Morin and Walczak [CPC 2021].

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

We will present a Product Structure Theorem for $k$-planar graphs, where a graph is $k$-planar if it has a drawing in the plane in which each edge is involved in at most $k$ crossings. In particular, every $k$-planar graph is a subgraph of the strong product of a graph of treewidth $O(k^5)$ and a path. The proof works in a much more general setting based on so-called shortcut systems, which may be helpful for developing product structure for other non-minor closed graph classes. This talk will discuss the proof of this theorem for graphs constructed from shortcut systems, the tools that it uses, and its consequences for other non-minor closed graph classes including map graphs, string graphs, powers of bounded-degree graphs, and 2-dimensional k-nearest neighbour graphs.

A class of graphs has "sublinear separators" if each of its $n$-vertex subgraphs has a balanced separator of size $\mathcal{O}(n^{1-\epsilon})$, for a fixed $\epsilon>0$. This property holds for classes with product structure, classes with a forbidden minor, and many types of geometric intersection graphs. But does every class with sublinear separators have a nice representation that displays all its separators? We find a new geometric representation which guarantees sublinear separators, generalizes most known constructions, and, unfortunately, still does not capture everything. Our approach is based on a connection with strong coloring numbers. This is joint work with Zden\v{e}k Dvo\v{r}\'{a}k and Sergey Norin.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

The planar graph product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood [J. ACM 2020] states that every planar graph is a subgraph of the strong product of a graph with bounded treewidth and a path. This result has been the key tool to resolve important open problems regarding queue layouts, nonrepetitive colourings, centered colourings, and adjacency labelling schemes. In this paper, we extend this line of research by utilizing shallow minors to prove analogous product structure theorems for several beyond planar graph classes. The key observation that drives our work is that many beyond planar graphs can be described as a shallow minor of the strong product of a planar graph with a small complete graph. In particular, we show that $k$ -planar, $(k, p)$-cluster planar, fan-planar and $k$-fan-bundle planar graphs can be described in this manner. Using a combination of old and new results, we deduce that these classes have bounded queue-number, bounded nonrepetitive chromatic number, polynomial $p$-centred chromatic numbers, linear strong colouring numbers, and cubic weak colouring numbers. In addition, we show that $k$-gap planar graphs have super-linear local treewidth and, as a consequence, cannot be described as a subgraph of the strong product of a graph with bounded treewidth and a path.

This video will be shown to in-person BIRS participants in KC 301. Virtual participants will receive a link and password to view the video at their leisure on Vimeo.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A quick application of the product structure theorem gives the best known bound for p-centered chromatic number of planar graphs, which is O(p^3log(p)). The r-th weak coloring number of planar graphs is bounded by O(r^3) but the proof applies another decomposition strategy known as chordal partitions. We are going to make an overview of the main proof ideas, recent developments, and complain about the most annoying open problems in the area.

I will sketch the main ideas of the product structure theorem of Krauthgamer and Lee for graphs with polynomial growth, and explore connections to other topics (expansion of products, asymptotic dimension, ...).

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Stanisław Ulam asked whether there exists a countable planar graph that contains every countable planar graph as a subgraph. János Pach~(1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain (i) an infinite complete graph as a minor, and (ii) a subdivision of the complete graph $K_t$, for every finite $t$. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite $n$-vertex subgraph has a balanced separator of size $O(\sqrt{n})$. The graph is the strong product of the universal treewidth-$6$ countable graph (which we define explicitly) and the 1-way infinite path. More generally, for every $t\in\mathbb{N}$ we construct a countable graph that contains every countable $K_t$-minor-free graph and has the above key properties. Our final contribution is a construction of a countable graph that contains every countable $K_t$-minor-free graph as an induced subgraph, has linear colouring numbers and linear expansion, and contains no subdivision of the countably infinite complete graph (implying (ii) above is best possible). This is joint work with Bojan Mohar, Robert Šámal, Carsten Thomassen, and David Wood.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Using a recent result on product structure of apex minor free graphs, we give simple proofs on clustered colourings of such graphs, more specifically those that exclude K_{s,t} as a subgraph.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.