BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Torsten Ueckerdt (Karlsruhe Institute of Technology)
DTSTART:20211122T160000Z
DTEND:20211122T165000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/1
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/1/">The planar graph product structure theorem</a>\nby Torsten Uec
 kerdt (Karlsruhe Institute of Technology) as part of BIRS workshop: Graph 
 Product Structure Theory\n\n\nAbstract\nI will prove the planar graph prod
 uct 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 w
 ith Wood & Yi [2021].\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Louis Esperet (CNRS)
DTSTART:20211122T173000Z
DTEND:20211122T180000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/2
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/2/">Nonrepetitive colourings of planar graphs</a>\nby Louis Espere
 t (CNRS) as part of BIRS workshop: Graph Product Structure Theory\n\n\nAbs
 tract\nA 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 differen
 t from the sequence of colours on the second half. One of the first applic
 ations of the product structure theorem was to show that planar graphs hav
 e nonrepetitive colourings with a bounded number of colours\, solving a pr
 oblem raised by Alon\, Grytczuk\, Haluszczak and Riordan in 2002. I will e
 xplain the ideas of the proof and show how to extend the result to classes
  of graphs that are closed under taking topological minors.\n\nThis is joi
 nt work with V. Dujmović\, G. Joret\, B. Walczak\, and D.R. Wood.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Wood (Monash University)
DTSTART:20211123T000000Z
DTEND:20211123T003000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/3
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/3/">Queue layouts of planar graphs (and beyond)</a>\nby David Wood
  (Monash University) as part of BIRS workshop: Graph Product Structure The
 ory\n\n\nAbstract\nWe show that planar graphs have bounded queue-number\, 
 thus proving a conjecture of Heath et al.\\ from 1992. The key to the proo
 f is the Planar Graph Product Structure Theorem: Every planar graph is a s
 ubgraph 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].\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:O-joung Kwon (Incheon National University)
DTSTART:20211123T003000Z
DTEND:20211123T010000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/4
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/4/">Reduced bandwidth: a qualitative strengthening of twin-width i
 n minor-closed classes (and beyond)</a>\nby O-joung Kwon (Incheon National
  University) as part of BIRS workshop: Graph Product Structure Theory\n\n\
 nAbstract\nIn 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 coloure
 d red. Bonnet\, Kim\, Thomassé\, and Watrigant [FOCS 2020] defined the tw
 in-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 gra
 ph $G$ to be the minimum integer $k$ such that there is a reduction sequen
 ce of $G$ in which every red graph has $f$ at most $k$. Our focus is on gr
 aph classes with bounded reduced-bandwidth\, which implies and is stronger
  than bounded twin-width (reduced-maximum-degree). \n\nWe show that every 
 proper minor-closed class has bounded reduced-bandwidth\, which is qualita
 tively stronger than a result of Bonnet et al.\\ for bounded twin-width. I
 n many instances\, we also make quantitative improvements using product st
 ructures. For example\, all previous upper bounds on the twin-width of pla
 nar graphs were at least $2^{1000}$. We show that planar graphs have reduc
 ed-bandwidth at most $466$ and twin-width at most $583$\; moreover\, we ca
 n obtain the witnessing reduction sequence in time $\\mathcal{O}(n\\log n)
 $. 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 bounde
 d reduced-bandwidth (irrespective of the degree of the vertices).\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwenaël Joret (Université Libre de Bruxelles)
DTSTART:20211123T160000Z
DTEND:20211123T165000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/5
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/5/">Sparse universal graphs for planarity</a>\nby Gwenaël Joret (
 Université Libre de Bruxelles) as part of BIRS workshop: Graph Product St
 ructure Theory\n\n\nAbstract\nThis talk focuses on the following two probl
 ems:\n\n(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).\n\n(2) Wh
 at is the minimum number of *vertices* in a graph containing all $n$-verte
 x planar graphs as *induced* subgraphs? Here Bonamy\, Gavoille\, and Pilip
 czuk (2019) recently established a $O(n^{4/3})$ bound.\n\nWe show that a b
 ound of $n^{1+o(1)}$ can be achieved for these two problems. Joint work wi
 th Vida Dujmović\, Louis Esperet\, Cyril Gavoille\, Piotr Micek\, and Pat
  Morin.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pat Morin (Carleton University)
DTSTART:20211123T173000Z
DTEND:20211123T182000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/6
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/6/">Optimal vertex ranking of planar graphs (and beyond)</a>\nby P
 at Morin (Carleton University) as part of BIRS workshop: Graph Product Str
 ucture Theory\n\n\nAbstract\nA (vertex) $\\ell$-ranking is a labelling $\\
 varphi:V(G)\\to\\mathbb{N}$ of the vertices of a graph $G$ with integer co
 lours 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\, f
 or which any 2-ranking requires $\\Omega(\\log n/\\log\\log\\log n)$ colou
 rs.  This result also extends to bounded genus graphs.  \n\nThese results 
 rely on product structure theorems showing that every planar (or bounded g
 enus) graph is contained in a graph product of the form $H\\boxtimes P\\bo
 xtimes K$ where $K$ is a fixed size clique\, P is a path\, and $H$ is a pl
 anar 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).\n
 \nIn developing this proof we obtain optimal bounds on the number of colou
 rs 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 inclu
 de new sublogarithmic upper bounds on the number of colours needed for $\\
 ell$-rankings of any graph with product structure\, including apex minor-f
 ree graphs and $k$-planar graphs.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Wood (Monash University)
DTSTART:20211124T000000Z
DTEND:20211124T005000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/7
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/7/">Graph product structure theory for minor-closed classes</a>\nb
 y David Wood (Monash University) as part of BIRS workshop: Graph Product S
 tructure Theory\n\n\nAbstract\nThe Planar Graph Product Structure Theorem 
 says that planar graphs are subgraphs of the strong product of a bounded t
 reewidth graph and a path\, which is to say they have bounded row treewidt
 h. This talk explores similar theorems for minor-closed classes that are m
 ore general than planar graphs. First\, I show that graphs of bounded Eule
 r genus have bounded row treewidth.  More generally\,  a minor-closed clas
 s has bounded row treewidth if and only if some apex graph is not in the c
 lass. I then show that graphs with bounded degree in any minor-closed clas
 s  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 bounde
 d.  This is joint work with Dujmović\, Joret\, Micek\, Morin and Ueckerdt
  [J. ACM 2020] and Dujmović\, Esperet\, Morin and Walczak [CPC 2021].\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pat Morin (Carleton University)
DTSTART:20211124T160000Z
DTEND:20211124T165000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/8
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/8/">Product structure for non-minor-closed classes</a>\nby Pat Mor
 in (Carleton University) as part of BIRS workshop: Graph Product Structure
  Theory\n\n\nAbstract\nWe will present a Product Structure Theorem for $k$
 -planar graphs\, where a graph is $k$-planar if it has a drawing in the pl
 ane 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 o
 f treewidth $O(k^5)$ and a path.  The proof works in a much more general s
 etting based on so-called shortcut systems\, which may be helpful for deve
 loping product structure for other non-minor closed graph classes.\n\nThis
  talk will discuss the proof of this theorem for graphs constructed from s
 hortcut systems\, the tools that it uses\, and its consequences for other 
 non-minor closed graph classes including map graphs\, string graphs\, powe
 rs of bounded-degree graphs\, and 2-dimensional k-nearest neighbour graphs
 .\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rose McCarty (University of Waterloo)
DTSTART:20211124T173000Z
DTEND:20211124T180000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/9
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/9/">Representing graphs with sublinear separators</a>\nby Rose McC
 arty (University of Waterloo) as part of BIRS workshop: Graph Product Stru
 cture Theory\n\n\nAbstract\nA class of graphs has "sublinear separators" i
 f each of its $n$-vertex subgraphs has a balanced separator of size $\\mat
 hcal{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 su
 blinear separators have a nice representation that displays all its separa
 tors? We find a new geometric representation which guarantees sublinear se
 parators\, generalizes most known constructions\, and\, unfortunately\, st
 ill does not capture everything. Our approach is based on a connection wit
 h strong coloring numbers. This is joint work with Zden\\v{e}k Dvo\\v{r}\\
 '{a}k and Sergey Norin.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robert Hickingbotham (Monash University)
DTSTART:20211125T003000Z
DTEND:20211125T010000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/10
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/10/">Shallow minors\, graph products and beyond planar graphs</a>\
 nby Robert Hickingbotham (Monash University) as part of BIRS workshop: Gra
 ph Product Structure Theory\n\n\nAbstract\nThe planar graph product struct
 ure theorem of Dujmović\, Joret\, Micek\, Morin\, Ueckerdt\, and Wood [J.
  ACM 2020] states that every planar graph is a subgraph of the strong prod
 uct of a graph with bounded treewidth and a path. This result has been the
  key tool to resolve important open problems regarding queue layouts\, non
 repetitive colourings\, centered colourings\, and adjacency labelling sche
 mes. In this paper\, we extend this line of research by utilizing shallow 
 minors to prove analogous product structure theorems for several beyond pl
 anar graph classes. The key observation that drives our work is that many 
 beyond planar graphs can be described as a shallow minor\nof the strong pr
 oduct of a planar graph with a small complete graph. In particular\, we sh
 ow that $k$ -planar\, $(k\, p)$-cluster planar\, fan-planar and $k$-fan-bu
 ndle planar graphs can be described in this manner. Using a combination of
  old and new results\, we deduce that these classes have bounded queue-num
 ber\, bounded nonrepetitive chromatic number\, polynomial $p$-centred chro
 matic numbers\, linear strong colouring numbers\, and cubic weak colouring
  numbers. In addition\, we show that $k$-gap planar graphs have super-line
 ar local treewidth and\, as a consequence\, cannot be described as a subgr
 aph of the strong product of a graph with bounded treewidth and a path.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Piotr Micek (Jagiellonian University)
DTSTART:20211125T160000Z
DTEND:20211125T165000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/11
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/11/">p-centred colourings</a>\nby Piotr Micek (Jagiellonian Univer
 sity) as part of BIRS workshop: Graph Product Structure Theory\n\nAbstract
 : TBA\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zdenek Dvorak (Charles University)
DTSTART:20211125T173000Z
DTEND:20211125T182000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/12
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/12/">On graphs with polynomial growth</a>\nby Zdenek Dvorak (Charl
 es University) as part of BIRS workshop: Graph Product Structure Theory\n\
 n\nAbstract\nI will sketch the main ideas of the product structure theorem
  of Krauthgamer and Lee for graphs with polynomial growth\, and explore co
 nnections to other topics (expansion of products\, asymptotic dimension\, 
 ...).\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tony Huynh (Monash University)
DTSTART:20211126T000000Z
DTEND:20211126T005000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/13
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/13/">Universal graphs for infinite planar graphs (and beyond)</a>\
 nby Tony Huynh (Monash University) as part of BIRS workshop: Graph Product
  Structure Theory\n\n\nAbstract\nStanisław Ulam asked whether there exist
 s a countable planar graph that contains every countable planar graph as a
  subgraph. János Pach~(1981) answered this question in the negative. We s
 trengthen 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$.\n\nOn the other hand\, we construct a countable graph that con
 tains all countable planar graphs and has several key properties such as l
 inear colouring numbers\, linear expansion\, and every finite $n$-vertex s
 ubgraph has a balanced separator of size $O(\\sqrt{n})$. The graph is the 
 strong product of the universal treewidth-$6$ countable graph (which we de
 fine explicitly) and the 1-way infinite path.  More generally\, for every 
 $t\\in\\mathbb{N}$ we construct a countable graph that contains every coun
 table $K_t$-minor-free graph and has the above key properties.\n\nOur fina
 l contribution is a construction of a countable graph that contains every 
 countable $K_t$-minor-free graph as an induced subgraph\, has linear colou
 ring numbers and linear expansion\, and contains no subdivision of the cou
 ntably infinite complete graph (implying (ii) above is best possible).\n\n
 This is joint work with Bojan Mohar\, Robert Šámal\, Carsten Thomassen\,
  and David Wood.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vida Dujmović (University of Ottawa)
DTSTART:20211126T160000Z
DTEND:20211126T165000Z
DTSTAMP:20260404T042105Z
UID:BIRS-21w5235/14
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/BIRS-
 21w5235/14/">Clustered colouring via products</a>\nby Vida Dujmović (Univ
 ersity of Ottawa) as part of BIRS workshop: Graph Product Structure Theory
 \n\n\nAbstract\nUsing a recent result on product structure of apex minor f
 ree graphs\, we give simple proofs on clustered colourings of such graphs\
 , more specifically those that exclude K_{s\,t} as a subgraph.\n
LOCATION:https://stable.researchseminars.org/talk/BIRS-21w5235/14/
END:VEVENT
END:VCALENDAR