Try laying out a square with all the vertices connected in a plane: it’s not possible. You must move one of the wires “up” a layer. Which wire? Great layout min

Try laying out a square with all the vertices connected in a plane: it’s not possible. You must move one of the wires “up” a layer. Which wire? Great layout minimizes layer transitions while also bunching together related HW blocks. The NP-completeness proof is related to work Knuth’s student (Plass?) did on laying out images in TeX.