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 multi-layer 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, and Aggarwal, Klawe, et al., we prove an upper-bound trade-off between these two quantities in a general multi-layer 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.