Rectilinear Steiner Tree Construction with Obstacles

Abstract

We propose a three-stage spanning-graph based algorithm to connect all pins with obstacles. At the first stage, we construct the spanning graph according to the given pins and the four corner points of the obstacles. At the second stage, the searching algorithm is performed to find a sub-graph, the spanning tree, and transform the spanning tree into a rectilinear Steiner tree at the third stage. The objective of the algorithm is to minimize the total wire-length. Compared with the results without obstacles, it shows experimentally that our algorithm can obtain the routing solution with only 1.4% extra total wire-length and 9.86% additional via counts with consideration of obstacles.