Catching Rats in \(H\)-minor-free Graphs

We show that every \(H\)-minor-free graph that also excludes a \((k \times k)\)-grid as a minor has treewidth/branchwidth bounded from above by a function \(f(t,k)\) that is linear in \(k\) and polynomial in \(t := |V(H)|\). Such a result was proven originally by [Demaine & Hajiaghayi, Combinatorica, 2008], where \(f\) was indeed linear in \(k\). However the dependency in \(t\) in this result was non-explicit (and huge). Later, [Kawarabayashi & Kobayashi, JCTB, 2020] showed that this bound can be estimated to be \(f(t,k) \in 2^{\mathcal O(t \log t)} \cdot k\). Wood recently asked whether \(f\) can be pushed further to be polynomial, while maintaining the linearity on \(k\). We answer this in a particularly strong sense, by showing that the treewidth/branchwidth of \(G\) is in \(\mathcal O(gk + t^{2304})\), where \(g\) is the Euler genus of \(H\). This directly yields \(f(t,k) = \mathcal O(t^2 k + t^{2304})\).