Theorem: For any fixed planar graph H, a maximum flow in an H-minor-free graph with n vertices can be computed in O(n) time.
Readers familiar with graph minors and maximum flows may want to try to prove this theorem themselves, before reading the following two-line proof.
Proof: Robertson and Seymour proved that any graph excluding a fixed planar graph as a minor has constant treewidth. Hagerup, Nishimura, Katajainen, and Ragde proved that maximum flows in graphs of constant treewidth can be computed in linear time. □
Sounds pretty cool, right? But now let's fill in some of those constants.
Suppose the graph H has k vertices. Classical results in graph drawing imply that H is a minor of a (2k-1)×(2k-1) grid; any graph that forbids H as a minor also forbids that grid. Robertson and Seymour proved that any graph with no r×r grid minor has treewidth at most 2O(r5). Hagerup et al. proved that a maximum flow in an n-vertex graph G can be computed in time 2O(t²) n, given a tree decomposition of G of width t. Finally, an algorithm of Bodlaender computes a tree decomposition of minimum width t in 2O(t³)n time. As far as I know, all of these upper bounds are the best known for their respective problems.
So the theorem should really be written like this:
Theorem: For any fixed planar k-vertex graph H, a maximum flow in an n-vertex H-minor-free graph can be computed in 22O(k5)n time.