Graph Steiner tree construction and its routing applications

A new heuristic algorithm is presented for graph Steiner tree problem (GSTP) with high quality solution. It consists of four steps based on tree splitting and merging. Then we apply this new heuristic algorithm to IC chip routing applications including obstacle-avoiding rectilinear Steiner minimal tree problem (OARSMT) for Manhattan architecture and obstacle-avoiding octilinear Steiner minimal tree problem (OAOSMT) for X-architecture. Through escape graph, OARSMT is converted to GSTP. We also propose several geometric transformations to construct OAOSMT from OARSMT. Experimental results show our heuristic algorithm for GSTP can get better solutions than traditional classic heuristic algorithms and our method to construct OAOSMT can reduce total wire length by at most 15%, compared with the wire length of OARSMT.