Planar multiple-valued decision diagrams
Tsutomu Sasao, Jon T. Butler · 2002
In VLSI, crossings 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 decision 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 binary decision diagrams.