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:20260422T185623Z
UID:BIRS-21w5235/1
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /1/">The planar graph product structure theorem</a>\nby Torsten Ueckerdt (
 Karlsruhe Institute of Technology) as part of BIRS workshop: Graph Product
  Structure Theory\n\n\nAbstract\nI will prove the planar graph product str
 ucture 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 join
 t work with Dujmovi’c\, Joret\, Micek\, Morin & Wood [2020] and with Woo
 d & Yi [2021].\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Louis Esperet (CNRS)
DTSTART:20211122T173000Z
DTEND:20211122T180000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /2/">Nonrepetitive colourings of planar graphs</a>\nby Louis Esperet (CNRS
 ) as part of BIRS workshop: Graph Product Structure Theory\n\n\nAbstract\n
 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 nonre
 petitive colourings with a bounded number of colours\, solving a problem r
 aised 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 gra
 phs that are closed under taking topological minors.\n\nThis is joint work
  with V. Dujmović\, G. Joret\, B. Walczak\, and D.R. Wood.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Wood (Monash University)
DTSTART:20211123T000000Z
DTEND:20211123T003000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/3
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /3/">Queue layouts of planar graphs (and beyond)</a>\nby David Wood (Monas
 h University) as part of BIRS workshop: Graph Product Structure Theory\n\n
 \nAbstract\nWe show that planar graphs have bounded queue-number\, thus pr
 oving a conjecture of Heath et al.\\ from 1992. The key to the proof is th
 e Planar Graph Product Structure Theorem: Every planar graph is a subgraph
  of the strong product of some treewidth 8 graph and some path.  We genera
 lise the first result to show that every proper minor-closed class has bou
 nded queue-number. This is joint work with Vida Dujmovi\\'c\, Gwena\\"el J
 oret\, Piotr Micek\, Pat Morin and Torsten Ueckerdt [J. ACM 67.4:22\, 2020
 ].\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:O-joung Kwon (Incheon National University)
DTSTART:20211123T003000Z
DTEND:20211123T010000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/4
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /4/">Reduced bandwidth: a qualitative strengthening of twin-width in minor
 -closed classes (and beyond)</a>\nby O-joung Kwon (Incheon National Univer
 sity) as part of BIRS workshop: Graph Product Structure Theory\n\n\nAbstra
 ct\nIn a reduction sequence of a graph\, vertices are successively identif
 ied until the graph has one vertex. At each step\, when identifying $u$ an
 d $v$\, each edge incident to exactly one of $u$ and $v$ is coloured red. 
 Bonnet\, Kim\, Thomassé\, and Watrigant [FOCS 2020] defined the twin-widt
 h of a graph $G$ to be the minimum integer $k$ such that there is a reduct
 ion 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 cla
 sses with bounded reduced-bandwidth\, which implies and is stronger than b
 ounded twin-width (reduced-maximum-degree). \n\nWe 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 structure
 s. For example\, all previous upper bounds on the twin-width of planar gra
 phs were at least $2^{1000}$. We show that planar graphs have reduced-band
 width at most $466$ and twin-width at most $583$\; moreover\, we can obtai
 n 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 t
 hat $d$-powers of graphs in a proper minor-closed class have bounded reduc
 ed-bandwidth (irrespective of the degree of the vertices).\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gwenaël Joret (Université Libre de Bruxelles)
DTSTART:20211123T160000Z
DTEND:20211123T165000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/5
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /5/">Sparse universal graphs for planarity</a>\nby Gwenaël Joret (Univers
 ité Libre de Bruxelles) as part of BIRS workshop: Graph Product Structure
  Theory\n\n\nAbstract\nThis talk focuses on the following two problems:\n\
 n(1) What is the minimum number of edges in a graph containing all $n$-ver
 tex 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) What is t
 he minimum number of *vertices* in a graph containing all $n$-vertex plana
 r graphs as *induced* subgraphs? Here Bonamy\, Gavoille\, and Pilipczuk (2
 019) recently established a $O(n^{4/3})$ bound.\n\nWe 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.
 \n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/5/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pat Morin (Carleton University)
DTSTART:20211123T173000Z
DTEND:20211123T182000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/6
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /6/">Optimal vertex ranking of planar graphs (and beyond)</a>\nby Pat Mori
 n (Carleton University) as part of BIRS workshop: Graph Product Structure 
 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 colours s
 o that for any path $u_0\,\\ldots\,u_p$ of length at most $\\ell$\, $\\var
 phi(u_0)\\neq\\varphi(u_p)$ or $\\varphi(u_0)<\\max\\{\\varphi(u_0)\,\\ldo
 ts\,\\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 inf
 initely many values of $n$\, there are $n$-vertex planar graphs\, for whic
 h any 2-ranking requires $\\Omega(\\log n/\\log\\log\\log n)$ colours.  Th
 is result also extends to bounded genus graphs.  \n\nThese results rely on
  product structure theorems showing that every planar (or bounded genus) g
 raph 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 gr
 aph 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 de
 veloping this proof we obtain optimal bounds on the number of colours need
 ed for $\\ell$-ranking graphs of treewidth $t$ and graphs of simple treewi
 dth $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$-ra
 nkings of any graph with product structure\, including apex minor-free gra
 phs and $k$-planar graphs.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:David Wood (Monash University)
DTSTART:20211124T000000Z
DTEND:20211124T005000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/7
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /7/">Graph product structure theory for minor-closed classes</a>\nby David
  Wood (Monash University) as part of BIRS workshop: Graph Product Structur
 e Theory\n\n\nAbstract\nThe Planar Graph Product Structure Theorem says th
 at planar graphs are subgraphs of the strong product of a bounded treewidt
 h 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 gen
 eral than planar graphs. First\, I show that graphs of bounded Euler genus
  have bounded row treewidth.  More generally\,  a minor-closed class has b
 ounded 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 Struct
 ure 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.  Thi
 s is joint work with Dujmović\, Joret\, Micek\, Morin and Ueckerdt [J. AC
 M 2020] and Dujmović\, Esperet\, Morin and Walczak [CPC 2021].\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pat Morin (Carleton University)
DTSTART:20211124T160000Z
DTEND:20211124T165000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/8
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /8/">Product structure for non-minor-closed classes</a>\nby Pat Morin (Car
 leton 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 plane in 
 which each edge is involved in at most $k$ crossings. In particular\, ever
 y $k$-planar graph is a subgraph of the strong product of a graph of treew
 idth $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.\n\nThis talk w
 ill discuss the proof of this theorem for graphs constructed from shortcut
  systems\, the tools that it uses\, and its consequences for other non-min
 or closed graph classes including map graphs\, string graphs\, powers of b
 ounded-degree graphs\, and 2-dimensional k-nearest neighbour graphs.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rose McCarty (University of Waterloo)
DTSTART:20211124T173000Z
DTEND:20211124T180000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/9
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /9/">Representing graphs with sublinear separators</a>\nby Rose McCarty (U
 niversity of Waterloo) as part of BIRS workshop: Graph Product Structure T
 heory\n\n\nAbstract\nA 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 cl
 asses with product structure\, classes with a forbidden minor\, and many t
 ypes of geometric intersection graphs. But does every class with sublinear
  separators have a nice representation that displays all its separators? W
 e find a new geometric representation which guarantees sublinear separator
 s\, generalizes most known constructions\, and\, unfortunately\, still doe
 s not capture everything. Our approach is based on a connection with stron
 g coloring numbers. This is joint work with Zden\\v{e}k Dvo\\v{r}\\'{a}k a
 nd Sergey Norin.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Robert Hickingbotham (Monash University)
DTSTART:20211125T003000Z
DTEND:20211125T010000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/10
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /10/">Shallow minors\, graph products and beyond planar graphs</a>\nby Rob
 ert Hickingbotham (Monash University) as part of BIRS workshop: Graph Prod
 uct Structure Theory\n\n\nAbstract\nThe planar graph product structure the
 orem of Dujmović\, Joret\, Micek\, Morin\, Ueckerdt\, and Wood [J. ACM 20
 20] 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 to
 ol to resolve important open problems regarding queue layouts\, nonrepetit
 ive 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 gr
 aph classes. The key observation that drives our work is that many beyond 
 planar graphs can be described as a shallow minor\nof the strong product o
 f 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 pl
 anar graphs can be described in this manner. Using a combination of old an
 d new results\, we deduce that these classes have bounded queue-number\, b
 ounded nonrepetitive chromatic number\, polynomial $p$-centred chromatic n
 umbers\, linear strong colouring numbers\, and cubic weak colouring number
 s. In addition\, we show that $k$-gap planar graphs have super-linear loca
 l treewidth and\, as a consequence\, cannot be described as a subgraph of 
 the strong product of a graph with bounded treewidth and a path.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Piotr Micek (Jagiellonian University)
DTSTART:20211125T160000Z
DTEND:20211125T165000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/11
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /11/">p-centred colourings</a>\nby Piotr Micek (Jagiellonian University) a
 s part of BIRS workshop: Graph Product Structure Theory\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zdenek Dvorak (Charles University)
DTSTART:20211125T173000Z
DTEND:20211125T182000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/12
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /12/">On graphs with polynomial growth</a>\nby Zdenek Dvorak (Charles Univ
 ersity) as part of BIRS workshop: Graph Product Structure Theory\n\n\nAbst
 ract\nI will sketch the main ideas of the product structure theorem of Kra
 uthgamer and Lee for graphs with polynomial growth\, and explore connectio
 ns to other topics (expansion of products\, asymptotic dimension\, ...).\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/12/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Tony Huynh (Monash University)
DTSTART:20211126T000000Z
DTEND:20211126T005000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/13
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /13/">Universal graphs for infinite planar graphs (and beyond)</a>\nby Ton
 y Huynh (Monash University) as part of BIRS workshop: Graph Product Struct
 ure Theory\n\n\nAbstract\nStanisław Ulam asked whether there exists a cou
 ntable planar graph that contains every countable planar graph as a subgra
 ph. János Pach~(1981) answered this question in the negative. We strength
 en this result by showing that every countable graph that contains all cou
 ntable planar graphs must contain (i) an infinite complete graph as a mino
 r\, 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 contains a
 ll countable planar graphs and has several key properties such as linear c
 olouring 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 ex
 plicitly) 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.\n\nOur final contr
 ibution is a construction of a countable graph that contains every countab
 le $K_t$-minor-free graph as an induced subgraph\, has linear colouring nu
 mbers and linear expansion\, and contains no subdivision of the countably 
 infinite complete graph (implying (ii) above is best possible).\n\nThis is
  joint work with Bojan Mohar\, Robert Šámal\, Carsten Thomassen\, and Da
 vid Wood.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vida Dujmović (University of Ottawa)
DTSTART:20211126T160000Z
DTEND:20211126T165000Z
DTSTAMP:20260422T185623Z
UID:BIRS-21w5235/14
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/BIRS-21w5235
 /14/">Clustered colouring via products</a>\nby Vida Dujmović (University 
 of Ottawa) as part of BIRS workshop: Graph Product Structure Theory\n\n\nA
 bstract\nUsing a recent result on product structure of apex minor free gra
 phs\, we give simple proofs on clustered colourings of such graphs\, more 
 specifically those that exclude K_{s\,t} as a subgraph.\n
LOCATION:https://researchseminars.org/talk/BIRS-21w5235/14/
END:VEVENT
END:VCALENDAR