Unconstrained multilayer switchbox routing

Consider the gradually more and more complexproblems of single row routing, channel routing and switchbox routing on the one hand, and the gradually less and less restrictivemodels (1-layer, Manhattan, unconstrained 2-layer, multilayer) on the other hand. The single row routing problems can always be solved in the Manhattan model, and the channel routing problem can always be solved in the unconstrained 2-layer model, in fact, both in linear time. In this paper, we show that the switchbox routing problem is solvable in the multilayer model, also in linear time.Supported in part by the Office of Naval Research (Grants N0001492J1375 and N0001492J4083) and by the Air Force Office of Scientific Research (Grants 89-0512B and F49620-93-1-0041).Research partially supported by the Hungarian National Foundation for Scientific Research (Grant No. OTKA 2118, 2505), and by the EC Cooperative Action IC 1000, Algorithms for Future Technologies (ALTEC).