Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI Original Research Article

Consider a planar grid of size image. The vertices of the grid are called terminals and pairwise disjoint sets of terminals are called nets. We aim at routing all nets in a cubic grid (above the original grid holding the terminals) in a vertex-disjoint way. However, to ensure solvability, it is allowed to extend the length and the width of the original grid to image and image by introducing image pieces of empty rows and columns between every two consecutive rows and columns containing the terminals. Hence the routing is to be realized in a cubic grid of size image. The objective is to minimize the height h. It is easy to show that the required height can be as large as image in the worst case. In this paper we show that if image then a routing with height image can always be found in polynomial time. Furthermore, the constant factor ‘6’ can be improved either by increasing the value of s or by limiting the number of terminals in a net. Possible trade-offs between s and h are discussed and the various constructions presented are compared by measuring the volumes of the routings obtained.