Linear bounds on treewidth in terms of excluded planar minors

One of the fundamental results in graph minor theory is that for every planar graph H, there is a minimum integer f (H) such that graphs with no minor isomorphic to H have treewidth at most f (H). A lower bound for f (H) can be obtained by considering the maximum integer k such that H contains k vertex-disjoint cycles. There exists a graph of treewidth (k k) which does not contain k vertex-disjoint cycles, from which it follows that f (H) = (k k). In particular, if f (H) is linear in V (H) for graphs H from a subclass of planar graphs, it is necessary that n-vertex graphs from the class contain at most O (n/ (n) ) vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an n-vertex graph H which is a disjoint union of r cycles, we show that f (H) 3n/2 + O (r² r), and improve this to f (H) n + O (n) when r = 2. In particular this bound is linear when r=O (n/ (n) ). We present a linear bound for f (H) when H is a subdivision of an r-edge planar graph for any constant r. We also improve the best known bounds for f (H) when H is the wheel graph or the 4 4 grid, obtaining a bound of 160 for the latter.