Crosstalk minimization in two-layer channel routing

As fabrication technology advances, devices and interconnection wires are placed in closer proximity and circuits operate at higher frequencies. This results in crosstalk between wire segments. Work on routing channels with reduced crosstalk is a very important area of current research. In this paper we show that the crosstalk minimization problem in the reserved two-layer Manhattan routing model is NP-complete, even for the channels without any vertical constraints. Since minimizing crosstalk is NP-complete, we propose simple and efficient polynomial time heuristic algorithms that reduce crosstalk more than 35% on average on a given routing solution of minimum area.