Motivated by recent developments regarding the product structure of planar graphs, we study relationships between treewidth, grid minors, and graph products. We show that the Cartesian product of any two connected $n$-vertex graphs contains an $\Omega(\sqrt{n})\times \Omega(\sqrt{n})$ grid minor. This result is tight: The lexicographic product (which includes the Cartesian product as a subgraph) of a star and any n-vertex tree has no $\omega(\sqrt{n})\times \omega(\sqrt{n})$ grid minor.
@article{10_37236_12822,
author = {Vida Dujmovi\'c and Pat Morin and David Wood and David Worley},
title = {Grid minors and products},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {2},
doi = {10.37236/12822},
zbl = {1566.05136},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12822/}
}
TY - JOUR
AU - Vida Dujmović
AU - Pat Morin
AU - David Wood
AU - David Worley
TI - Grid minors and products
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/12822/
DO - 10.37236/12822
ID - 10_37236_12822
ER -
%0 Journal Article
%A Vida Dujmović
%A Pat Morin
%A David Wood
%A David Worley
%T Grid minors and products
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12822/
%R 10.37236/12822
%F 10_37236_12822
Vida Dujmović; Pat Morin; David Wood; David Worley. Grid minors and products. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/12822
