# LINEAR TIME ALGORITHMS FOR OPTIMAL CMOS LAYOUT.

Published

Journal Article

We consider the problem of efficient CMOS circuit layout which has been formulated into an interesting graph-theoretical problem. A linear-time algorithm is described for optimal layout of a graph when the circuit topology is fixed. A further linear-time algorithm is provided to determine an optimal layout (i. e. , having no diffusion gaps) when such a layout exists in some topology for the circuit. The key to our solution is a finite set of representative graphs which concisely describe topologically distinct paths in planar embedded series-parallel graphs.

### Duke Authors

### Cited Authors

- Ravi Nair, ; Bruss, A; Reif, J

### Published Date

- December 1, 1985

### Start / End Page

- 327 - 338

### Citation Source

- Scopus