In boundary single-layer routing with slidable or permutable terminals (BSLR-S or BSLR-P), the assumption that each net may have more than one terminal in a range or cluster should be removed. An example that shows Pick-Closest might report "unsolvable" for a solvable instance is considered. It is clear that the instance is solvable if (and only if) the two terminals of net N/sub 1/ are assigned to vertices c and d. However, Pick-Closest will assign the two terminals of net N/sub 1/ to vertices /spl lcub/b,c/spl rcub/ or /spl lcub/d,e/spl rcub/, then report "unsolvable" due to the failure in routing net N/sub 2/. Thus, Pick-Closest only works in instances when each net has at most one terminal in a range. Since BSLR-P also includes slidable terminals, we employ Pick-Closest to solve BSLR-P when TR-permutation is determined by Greedy-Assignment. Thus in BSLR-P, each net can have at most one terminal in a cluster as well. The time complexity of the problem of boundary single-layer routing with slidable and permutable terminals remains open if a net is allowed to have multiple terminals in a cluster.>

We introduce the single-layer global routing problem (SLGRP), also called homotopic routing or rubber-band-equivalent routing, and propose a technique for solving it. Given a set of nets, the proposed technique first determines the routing sequence based on the estimated congestion, the bounding-box length and priority. Then, it finds a routing path, being a sequence of tiles, for each net (one net at a time), avoiding "congested" areas. The overall goal of the algorithm is to maximize the number of routed nets. The proposed global router is the first true single-layer global router ever reported in the literature. The size of tiles, w/spl times/w, is an input parameter in our algorithm. For w=1, the proposed global router serves as an effective detailed router. An optimal postprocessing algorithm, minimizing wire length and number of bends, under homotopic transformation, is presented. The technique has been implemented and tried out for randomly generated data. The algorithm is very efficient and produces good results.>

The author introduces the two-layer via-free routing problem (2LVFRP) and proposes an optimal algorithm to solve it. Given a set of nets (with terminals on the boundary) and two layers for routing them, the algorithm determines the layer assignment and detailed routing for each net such that no via is needed, if such solution exists.>

The authors study a generalization of previous results on the boundary single-layer routing (BSLR) problem. In the BSLR problem, there is a planar graph, a collection of terminals on the boundary of the infinite face, and a set of multiterminal nets. A solution of BSLR consists of a set of vertex disjoint trees interconnecting the terminals belonging to the same (multiterminal) net. An algorithm, unifying and generalizing previous BSLR algorithms, to solve an arbitrary instance of BSLR, is presented. Problems involving slidable terminals (i.e. when terminals can slide within a certain range on the boundary) and permutable terminals (i.e. when positions of some terminals (going to the same gate) can be interchanged) are optimally solved. The proposed algorithm runs in O(e) time, where e is the number of edges in the input graph. The results are extended to handle gridless routing environments.>