An improved bound on the treewidth of planar graphs excluding a grid minor

Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret +3

We show that every planar graph with no $t\times t$ grid minor has treewidth at most $4t+4$. This improves on the previously best known bound of $\frac{9}{2}t-\frac{11}{2}$, du…