IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 1 Efficient Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Geometric Reduction

Abstract—Given a set of pin-vertices, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects all the pin-vertices possibly through Steiner points using vertical and horizontal segments with the minimal wirelength and with-out intersecting any obstacle. To deal with multiple rout-ing layers and preferred routing orientations, we consider the multilayer OARSMT (ML-OARSMT) problem and the obstacle-avoiding preferred direction Steiner tree (OAPD-ST) problem. First, we prove that the multilayer case is theo-retically different from the 2D one, and propose a reduc-tion to transform a multilayer instance into a 3D instance. Based on the reduction, we apply computational geometry techniques to develop an efficient algorithm, utilizing exist-ing OARSMT heuristics, for the ML-OARSMT problem and the OAPD-ST problem. Furthermore, we develop an advanced Steiner point selection to avoid inferior Steiner points and to improve the solution quality. Experimental results show that our algorithm provides a solution with excellent quality and has a significant speed-up compared to previously known results. Index Terms—Obstacle-avoidance, physical design, rectilinear Steiner minimal tree (RSMT), routing. I