Title :
Routing in rectilinear polygons
Author_Institution :
Dept. of Electr. Eng., North Carolina Univ., Charlotte, NC, USA
Abstract :
The author presents an algorithm for routing nets in a generic rectilinear polygon. The algorithm constructs a routing if one exists. The number of wire bends in the constructed routing is minimized and is upper bounded by O(m). The time complexity of the algorithm is O(m log2m), where m is the number of vertices on the boundary of the polygon. The algorithm can be applied to many VLSI routing problems, such as switch-box, channel, junction, and convex grids routings
Keywords :
VLSI; circuit layout; network topology; VLSI routing problems; channel routeings; convex grids routings; junction routeings; rectilinear polygons; switch-box; time complexity; Routing; Switching circuits; Very large scale integration; Virtual colonoscopy; Wire;
Conference_Titel :
Circuits and Systems, 1991., IEEE International Sympoisum on
Print_ISBN :
0-7803-0050-5
DOI :
10.1109/ISCAS.1991.176251
