Local routing of two-terminal nets is easy (extended abstract)
Kaufmann, Michael, Kurt Mehlhorn · Publications of the UdS (Saarland University) · 1984
A local routing problem is given by a routing region (a subgraph of the planer grid) and a set of nets. For each net a global routing is also given. The problem is to find a local routing which is consistent with the global routing (if there is one). In this paper we show that local routing problems can be sloved in time O(n(log n)2).