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.

  • 0
    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? Thanks2012-01-08
  • 1
    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).2012-01-08
  • 0
    Can you give an example where some class of graphs is some other class of graphs minor free and therefore some calculation is simplified?2012-01-13
  • 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