On Routing Two-Terminal Nets in the Presence of Obstacles.

We consider the problem of routing k two-terminal nets in the presence of obstacles in two models: the standard two-layer model and the knock-knee model. Determining routability is known to be NP-complete for arbitrary k. Our main results are polynomial time algorithms to determine whether the given nets are routable in either model for any fixed k. We introduce a technique that reduces the general problem into finding edge-disjoint paths in a graph whose size is proportional to the size of the obstacles. Two optimization criteria are considered: the total length of the wires and the number of vias used