Topological Routing Path Search Algorithm with Incremental Routability Test

Abstract | This article describes a topological rout-ing path search algorithm embedded in our auto-router for printed circuit boards. The algorithm searches for a topological path that is guaranteed to be transformable into a physical wire satisfying de-sign rules. We propose a method for incrementally verifying design rules during topological path search in a graph based on constrained Delaunay triangula-tion, and describe several improvements to the routing path search algorithm that remedy the overhead of the routability test and avoid combinatorial explosion. I