[For the entire collection see Zbl 0555.00010.]
A new less-complexity algorithm for an optimal VLSI layout (i.e. minimal width layout) of CMOS functional cells is presented. The CMOS cells considered implement negative unate Boolean functions and are logically represented by a composition of two, mutually dual series-parallel networks of transistors. The problem of optimal layout of such a class of CMOS cells, originally stated by T. Uehara and W. M. van Cleemput [IEEE Trans. Comput. C-30, 305-312 (1981)] has been reformulated here in graph-theoretical terms. Let us denote by \(G_ d\) the dual of the series-parallel graph G. A complete set of paths for a graph G is a set of paths which covers every edge in G exactly once. A complete set of paths in \((G,G_ d)\) is a complete set for both G as well as \(G_ d\). A d-Euler path is an Euler parth in a graph G such that the corresponding sequence of edges forms an Euler path in \(G_ d\). Graph G will then be referred to as d-Eulerian. The goal of the algorithm is to find a minimal complete set of paths in \((G,G_ d)\). The algorithm consists in a composition process for special reduced forms of typical graph structures. If in some cases the input graph may be rearranged to form a d-Eulerian graph, then this constitutes the solution. In such cases the algorithm takes time that is linear in the number of components in the graph being connected in series.