ABSTRACT
Associated with the rapid improvement of fine-line etching techniques, both the wire density and the number of routing layers have been skyrocketing. Steiner's problem with rectilinear distance is an infamous NP problem. It was usually reduced to subproblems, or was approximated by improving a minimum spanning tree to reduce tree length by about 8% on average. This chapter gives the definitions pertaining to Steiner points, edge-sets and edge-set trees, and discusses properties of Steiner points in an no-redundancy edge-set tree. Then develops graph arithmetics for generating a no-redundancy edge-set tree, and generating other no-redundancy edge-set trees, by replacing edge-sets and cliques of the no-redundancy edge-set tree with other edge-sets and cliques. Finally describes the general solution contained by all no-redundancy edge-set trees, and provides procedures for finding no-redundancy edge-set trees, as well as an example of finding the general solution for 10 nodes.
