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;VALUE=DATE-TIME:20211122T160000Z
DTEND;VALUE=DATE-TIME:20211122T165000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/1
DESCRIPTION:Title: The planar graph product structure theorem\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;VALUE=DATE-TIME:20211122T173000Z
DTEND;VALUE=DATE-TIME:20211122T180000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/2
DESCRIPTION:Title: Nonrepetitive colourings of planar graphs\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;VALUE=DATE-TIME:20211123T000000Z
DTEND;VALUE=DATE-TIME:20211123T003000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/3
DESCRIPTION:Title: Queue layouts of planar graphs (and beyond)\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;VALUE=DATE-TIME:20211123T003000Z
DTEND;VALUE=DATE-TIME:20211123T010000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/4
DESCRIPTION:Title: Reduced bandwidth: a qualitative strengthening of twin-width in minor
-closed classes (and beyond)\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;VALUE=DATE-TIME:20211123T160000Z
DTEND;VALUE=DATE-TIME:20211123T165000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/5
DESCRIPTION:Title: Sparse universal graphs for planarity\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;VALUE=DATE-TIME:20211123T173000Z
DTEND;VALUE=DATE-TIME:20211123T182000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/6
DESCRIPTION:Title: Optimal vertex ranking of planar graphs (and beyond)\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;VALUE=DATE-TIME:20211124T000000Z
DTEND;VALUE=DATE-TIME:20211124T005000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/7
DESCRIPTION:Title: Graph product structure theory for minor-closed classes\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;VALUE=DATE-TIME:20211124T160000Z
DTEND;VALUE=DATE-TIME:20211124T165000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/8
DESCRIPTION:Title: Product structure for non-minor-closed classes\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;VALUE=DATE-TIME:20211124T173000Z
DTEND;VALUE=DATE-TIME:20211124T180000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/9
DESCRIPTION:Title: Representing graphs with sublinear separators\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;VALUE=DATE-TIME:20211125T003000Z
DTEND;VALUE=DATE-TIME:20211125T010000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/10
DESCRIPTION:Title: Shallow minors\, graph products and beyond planar graphs\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;VALUE=DATE-TIME:20211125T160000Z
DTEND;VALUE=DATE-TIME:20211125T165000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/11
DESCRIPTION:Title: p-centred colourings\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;VALUE=DATE-TIME:20211125T173000Z
DTEND;VALUE=DATE-TIME:20211125T182000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/12
DESCRIPTION:Title: On graphs with polynomial growth\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;VALUE=DATE-TIME:20211126T000000Z
DTEND;VALUE=DATE-TIME:20211126T005000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/13
DESCRIPTION:Title: Universal graphs for infinite planar graphs (and beyond)\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;VALUE=DATE-TIME:20211126T160000Z
DTEND;VALUE=DATE-TIME:20211126T165000Z
DTSTAMP;VALUE=DATE-TIME:20211209T082638Z
UID:BIRS-21w5235/14
DESCRIPTION:Title: Clustered colouring via products\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