@inproceedings{AdlerGroKre08,
  abstract = "By Robertson and Seymour's graph minor theorem, every minor ideal can be characterised by a finite family of excluded minors. (A <i>minor ideal</i> is a class of graphs closed under taking minors.) We study algorithms for computing excluded minor characterisations of minor ideals. We propose a general method for obtaining such algorithms, which is based on definability in monadic second-order logic and the decidability of the monadic second-order theory of trees. A straightforward application of our method yields algorithms that, for a given <i>k</i>, compute excluded minor characterisations for the minor ideal <i>T_k</i> of all graphs of tree width at most <i>k</i>, the minor ideal <i>B_k</i> of all graphs of branch width at most <i>k</i>, and the minor ideal <i> G_k</i> of all graphs of genus at most <i>k</i>. Our main results are concerned with constructions of new minor ideals from given ones. Answering a question that goes back to Fellows and Langston, we prove that there is an algorithm that, given excluded minor characterisations of two minor ideals C and D, computes such a characterisation for the ideal C\cup D. Furthermore, we obtain an algorithm for computing an excluded minor characterisation for the class of all apex graphs over a minor ideal C, given an excluded minor characterisation for C. (An apex graph over C is a graph G from which one vertex can be removed to obtain a graph in C.) A corollary of this result is a uniform ftp-algorithm for the ``distance k from planarity'' problem.",
  author = "Isolde Adler and Martin Grohe and Stephan Kreutzer",
  booktitle = "ACM-SIAM Symposium on Discrete Algorithms (SODA)",
  title = "Computing Excluded Minors",
  url = "http://web.comlab.ox.ac.uk/oucl/work/stephan.kreutzer/Publications/08-soda.pdf",
  year = "2008",
}