Planar Decision Diagrams for Multiple-Valued Functions

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 for produce planar multiple-valued circuits. Specifically, we show conditions on 1) threshold funtions, 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 two-valued monotone increasing threshold functions of up to five variables have planar ordered binary decision diagrams.