4
$\begingroup$

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

  • 0
    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](http://en.wikipedia.org/wiki/Minor_%28graph_theory%29#Major_results_and_conjectures), especially the second and third paragraphs, to see some of the useful effects.2012-01-07

1 Answers 1

2

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.

  • 1
    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 computations2012-01-14