Take the 2-minute tour ×

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

share|improve this question
Typically in a particular context $H$ is fixed, or is at worst a member of a fixed class of graphs. Take a look at this link, especially the second and third paragraphs, to see some of the useful effects. –  Brian M. Scott Jan 7 '12 at 20:22

1 Answer 1

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.

share|improve this answer
Thank you for your answer. You wrote "it can be quite difficult to determine the structure". Which structure are you referring to here? Do you mean that one still has to argue that one can make use of this fact by deriving a concrete algorithm? I thought there exist some theorems (like Demaines Bidimensionality) which are more or less straight forward to apply. Do you know any good literature about this topic it seam interesting? Thanks –  roman Jan 8 '12 at 14:43
Yes, because the constants involved can be quite painful. That's why it's easier to focus on specific graph classes (like bounded treewidth for example). –  Suresh Venkat Jan 8 '12 at 20:57
Can you give an example where some class of graphs is some other class of graphs minor free and therefore some calculation is simplified? –  Graphth Jan 13 '12 at 22:13
Well bounded treewidth graphs are free of "grid minors". Specifically a graph of treewidth k cannot have a $k+1 \times k+1$ grid inside it. On such graphs, it's easier to do various computations –  Suresh Venkat Jan 14 '12 at 1:33

Your Answer


