One-dimensional logic gate assignment and interval graphs

This paper gives a graph-theoretic approach to the design of one-dimensional logic gate arrays using MOS or units. The incidence relation between gates and nets is represented by a graph , and a possible layout of gates and nets is characterized by an interval graph , where is called an augmentation. It is shown that the number of tracks required for between-gate wiring is equal to the clique number (chromatic number) of , and hence the optimum placement problem is converted to that of minimum clique number augmentation. This turns out to be an -complete problem. Instead a polynomial-time algorithm for finding a minimal augmentation is presented, where an augmentation is minimal if no proper subset of it is an augmentation. An algorithm for gate sequencing with respect to a given augmentation is also presented.