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 I2L units. The incidence relation between gates and nets is represented by a graph H = (V, E), and a possible layout of gates and nets is characterized by an interval graph H- (V, E U F), where F 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 H, and hence the optimum placement problem is converted to that of minimum clique number augmentation. This turns out to be an N P-complete problem. Instead a polynomial-time algorithm for finding a minimal augmentation is presented, where an augmentation is minimal no proper subset of it is an augmentation. An algorithm for gate sequencing with respect to a given augmentation is also presented. © 1979 IEEE