Efficient construction of minimal Spanning Tree avoiding rectilinear directional obstacles

Recently, the obstacle avoidance in the minimum spanning tree (MST) problem, which is one of the most important CAD problems, has been received a great deal of attention. In general, this obstacle avoiding MST (OAMST) can be efficiently found as a sub-graph of a spanning grap (OASG) which is constructed by connecting neighboring pins and obstacle corners. Unfortunately, its application was quite limited since obstacles were restricted to be rectangular, and prohibit wiring routes from passing through them in both horizontal and vertical dimensions. In this paper, the problem is extended so that the obstacles may have rectilinear shapes, and allow wiring routes passing through them either in the horizontal or vertical dimension. A finite state machine-based approach is proposed to recognize the complicated obstacle patterns, and precisely create edges that construct the OASG. Two algorithms from previous work have been modified to include this approach without increasing the computational complexity. The proposed approach and algorithm have been implemented and validated on a comprehensible set of nets that are sampled from an industrial strength system-on-chip design.