3-dimensional Channel Routing

Consider two parallel planar grids of size w × n . The vertices of these grids are called terminals and pairwise disjoint subsets of termi nals are called nets. We aim at routing all nets in a cubic grid between the two layers h olding the terminals. However, to ensure solvability, it is allowed to introduce a n empty row/column be- tween every two consecutive rows/columns containing the te rminals (in both grids). Hence the routing is to be realized in a cubic grid of size 2 n × 2 w × h . The objective is to minimize the height h . In this paper we generalize previous results of Recski and Szeszl ́er [10] and show that every problem instance is so lvable in polynomial time with height h = O (max( n, w )). This linear bound is best possible (apart from a constant factor)