Some polynomially solvable subcases of the detailed routing problem in VLSI design

There are plenty of NP-complete problems in VLSI design, like channel routing or switchbox routing in the 2-layer Manhattan model (2Mm, for short). However, there are quite a few polynomially solvable problems as well. Some of them (like the single row routing in 2Mm) are “classical” results; in this survey we present some more recent ones, including 1.a linear time channel routing algorithm in the unconstrained 2-layer model2.a linear time switchbox routing algorithm in the unconstrained multilayer model3.a linear time solution of the so called gamma routing problem in 2Mm(This latter means that all the terminals to be interconnected are situated at two adjacent sides of a rectangular routing area, thus forming a V shape. Just like channel routing, it is (i) a special case of switchbox routing, and (ii) contains single row routing as a special case.)We present the (positive and negative) results in a systematic way, taking into account two hierarchies, namely that of geometry (what to route) and technology (how to route) at the same time.