Topological routing path search algorithm with incremental routability test

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.