the interconnection problem - a tutorial
This paper represents a fairly extensive survey of the literature on the interconnection problem. The topics covered are: Pin Assignment, Layering, Ordering, Wire List Determination, Spanning Trees, Rectilinear Steiner Trees and Wire Layout. In addition, several new ideas are presented which could provide for better wire layout. Algorithms are presented in a way that makes them easy to understand and hence, to discuss and apply. Formal statement of the algorithms can be found in the references cited.
interconnect tutorial paper survey assignment layer order determinism spanning tree trees layout algorithm formalism