Title :
Topological routing path search algorithm with incremental routability test
Author :
Hama, Toshiyuki ; Etoh, Hiroaki
Author_Institution :
Res. Lab., IBM Japan Ltd., Tokyo, Japan
Abstract :
The article describes a topological routing path search algorithm embedded in the auto-router for printed circuit boards. The algorithm searches for a topological path that is guaranteed to be transformable into a physical wire satisfying design rules. The authors propose a method for incrementally verifying design rules during topological path search in a graph based on constrained Delaunay triangulation, and describe several improvements to the routing path search algorithm that remedy the overhead of the routability test and avoid combinatorial explosion
Keywords :
circuit layout CAD; mesh generation; network routing; network topology; printed circuit layout; printed circuit testing; auto-router; constrained Delaunay triangulation; design rules; graph; incremental design rule verification; incremental routability test; physical wire; printed circuit boards; routability test overhead; topological routing path search algorithm; Algorithm design and analysis; Circuit testing; Data structures; Electronic mail; Explosions; Laboratories; Printed circuits; Routing; Wires; Wiring;
Conference_Titel :
Design Automation Conference, 1997. Proceedings of the ASP-DAC '97 Asia and South Pacific
Conference_Location :
Chiba
Print_ISBN :
0-7803-3662-3
DOI :
10.1109/ASPDAC.1997.600349
