Recently I cam across a statement which divides graphs into different classes w.r.t. the complexity of problems on them.
planar < bounded genus < H-minor free < general graphs
My question regards the definition of H-minor free graphs. What I don't understand is that apparently H is not fixed.
Is it true that as long as I can be sure that my (large) graph G doesn't contain some! minor, then some problems might be easier to compute on G then on general graphs regardless of what the actual minor is?
Thank you
Your statement is correct. If there's a class of graphs that excludes some H-minor (for any H), then this class has special structure that in principle will lead to more efficient algorithms. The "in principle" part is the killer though, since it can be quite difficult to determine the structure in order to exploit it.