Topological routing path search algorithm with incremental routability test

This paper describes a topological routing path search algorithm embedded i n our rubber-band-based autorouter for single-layer printed circuit boards, The algorithm searches for a topological path that is guaranteed to be tra nsformable into a physical wire satisfying design rules. Topological path s earch algorithms used in existing autorouters verify design rules only loca lly and approximately. However, it is preferable to satisfy design rules ex actly in the global routing phase, especially for routing a densely wired p rinted circuit board. We propose a method for incrementally verifying desig n rules during the topological routing path search and describe several imp rovements to the algorithm that reduce the overhead of the routability test and suppress combinatorial explosion. We also discuss the practical feasib ility of the proposed algorithm on the basis of the results of experiments using several printed circuit boards.