Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI
Consider a planar grid of size wn w  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?=sw w ? = sw and n?=sn n ? = sn by introducing s-1 s - 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 (sn)(sw)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?2 s ? 2 then a routing with height h = 6 max ( 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.
vlsi layout 3-d routing