# Computing Excluded Minors

*Isolde Adler‚ Martin Grohe and Stephan Kreutzer*

### Abstract

By Robertson and Seymour's graph minor theorem, every minor ideal can be characterised by a finite family of excluded minors. (A *minor ideal* 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 *k*, compute excluded minor characterisations for the minor ideal *T_k* of all graphs of tree width at most *k*, the minor ideal *B_k* of all graphs of branch width at most *k*, and the minor ideal * G_k* of all graphs of genus at most *k*. 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∪ 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.