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

Consider a planar grid of size w×nw×n. 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 w′=sww′=sw and n′=snn′=sn by introducing s-1s-1 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 (s·n)×(s·w)×h(s·n)×(s·w)×h. The objective is to minimize the height h  . It is easy to show that the required height can be as large as h=Ω(max(n,w))h=Ω(max(n,w)) in the worst case. In this paper we show that if s≥2s≥2 then a routing with height h=6max(n,w) 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.