{"id":"arxiv/2609.15596","url":"https://arxiv.org/abs/2609.15596","tags":["math.CO","cs.DM"],"score":0,"title":"An improved bound on the treewidth of planar graphs excluding a grid minor","domain":"math.CO","source":"arxiv","authors":["Wouter Cames van Batenburg","Quentin Claus","Gwenaël Joret","Robin Petit","Jean-Florent Raymond","Eileen Robinson"],"reviews":0,"subject":"math.CO","summary":"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}$, due to Gu and Tamaki (2012), and is within a factor $2$ of optimal. A key step in the proof is showing the following result, which might be of independent interest: Every $2$-connected plane graph $G$ with radius $d$ and faces of size at most $k$ has a tree-decomposition of width at most $\\max\\{3d+ k+5, 2d+2k+1\\}$ such that the vertex set of every face of $G$ is contained in some bag.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}