
Summary: 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 \textit{M. Cutler} and \textit{Y. Shiloach} [Networks 8, 253-278 (1978; Zbl 0404.05002)], \textit{A. Aggarwal, M. Klawe, D. Lichtenstein, N. Linial} and \textit{A. Wigderson} [Algorithmica 6, 241-255 (1991; Zbl 0711.68054)] and \textit{A. Aggarwal, M. Klawe} and \textit{P. Shor} [Algorithmica 6, 129-151 (1991; Zbl 0703.68044)], 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.
Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), VLSI layout, combinatorial optimization, disjoint paths problem, Nonnumerical algorithms
Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), VLSI layout, combinatorial optimization, disjoint paths problem, Nonnumerical algorithms
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 18 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
