Planar Decision Diagrams for Multiple-Valued Functions
Jon T. Butler, Tsutomu Sasao · 1996
Abstract : In VLSI, crossings of interconnect occupy space and cause delay. Therefore, there is significant benefit to planar circuits. We propose the use of planar multiple-valued decision diagrams to produce planar multiple-valued circuits. Specifically, we show conditions on: (1) threshold functions, (2) symmetric functions, and (3) monotone increasing functions that produce planar diagrams. Our results apply to binary functions, as well. For example, we show that all two-valued monotone increasing threshold functions of up to five variables have planar ordered binary decision diagrams.