We consider the development of practical algorithms based on the theory of graph minors. Although an exact decision algorithm using this approach would generally require testing to ensure the absence of a prohibitively large number of obstructions, approximate algorithms can be designed that test for only a few obstructions. Efficient self-reduction strategies can then be incorporated to approximate a solution to the problem at hand.

In this paper, we investigate a prototypical problem, that of finding a three-track gate matrix layout for VLSI circuits. We design a streamlined test for a half dozen of the densest obstructions, thereby approximating an exact algorithm that would require over one hundred such tests, many of which appear very difficult.

In this effort, we have also built a software package to automate the use of our tools. Experimental results obtained using this package demonstrate that it is extremely fast and suggest that, despite its theoretical limitations, its results are correct most of the time.