The Feasibility and Use of a Minor Containment Algorithm

Abstract

We present a general algorithm for checking whether one graph is a minor of another. Although this algorithm is not polynomial-time, it is quite practical for small graphs. For all connected graphs with 5 vertices or less we count how many connected graphs of order at most 9 are above them in the minor order. Our computed tables may be useful in the design of heuristic algorithms for minor closed families of graphs.