Bridge obstructions to circular-three gate matrix layout (Q1393029)

This paper studies a variant of the gate matrix layout problem, a problem motivated from finding layouts of logical circuits on a chip. A permutation of columns of a matrix must be found that minimizes the number of tracks, which is the maximum number of 1's in a column, after doing a fill-in. In this variant of the gate matrix layout problem, one turns a number of 0's into 1's, such that all 1's appear at consecutive positions, assuming the columns are ordered circularly, i.e., the last column is assumed to be next to the first column. For every fixed \(k\), the class of graphs representing a matrix with a solution with at most \(k\) tracks is closed under taking minors. Such classes have (by the graph minor theory of Robertson and Seymour) a finite obstruction set. In this paper, a set of 336 graphs that belong to the obstruction set for the circular gate matrix layout problem with three tracks are given. These are all obstructions that fulfil a certain criteria, namely that they contain a bridge that separates sufficiently large subgraphs.