New algorithms for the rectilinear Steiner tree problem

An approach to constructing the rectilinear Steiner tree (RST) of a given set of points in the plane, starting from a minimum spanning tree (MST), is discussed. The main idea in this approach is to find layouts for the edges of the MST that maximize the overlaps between the layouts, thus minimizing the cost (i.e. wire length) of the resulting rectilinear Steiner tree. Two algorithms for constructing rectilinear Steiner trees from MSTs, which are optimal under the conditions that the layout of each edge of the MST is an L shape or any staircase, respectively, are described. The first algorithm has linear time complexity and the second algorithm has a higher polynomial time complexity. Steiner trees produced by the second algorithm have a property called stability, which allows the rerouting of any segment of the tree, while maintaining the cost of the tree, and without causing overlaps with the rest of the tree. Stability is a desirable property in VLSI global routing applications