Node-disjoint paths on the mesh and a new trade-off in VLSI layout

Abstract

A number of basic models for VLSI layout are based on the construction of node-disjoint paths between terminals on a multilayer grid. In this setting, one is interested in minimizing both the number of layers required and the area of the underlying grid. Building on work of Cutler and Shiloach [Networks, 8 (1978), pp. 253-278], Aggarwal et al. [Proc. 26th IEEE Symposium on Foundations of Computer Science, Portland, OR, 1985; Algorithmica, 6 (1991), pp. 241-255], and Aggarwal, Klawe, and Shor [Algorithmica, 6 (1991), pp. 129-151], we prove an upper-bound trade-off between these two quantities in a general multilayer grid model. As a special case of our main result, we obtain significantly improved bounds for the problem of routing a full permutation on the mesh using node-disjoint paths; our new bound here is within polylogarithmic factors of the bisection bound. Our algorithms involve some new techniques for analyzing the structure of node-disjoint paths in planar graphs and indicate some respects in which this problem, at least in the planar case, is fundamentally different from its edge-disjoint counterpart.