Topological Routing amidst Polygonal Obstacles

This paper presents a fast graph-traversal based greedy approach for solving the problem of topologi-cal routing in the presence of polygonal obstacles. The polygonal obstacles represent pre-routed nets or groups of circuit blocks. Routing paths for all the nets are con-structed incrementally and concurrently. Design rules for separation are modeled as constraints on edges and vertices. The experimental results obtained are very encouraging.