A Weighted Directed Graph-based Algorithm for Group Routing in Printed Circuit Boards

Routing is considered an essential component in the design of printed circuit boards. In traditional research, a primary focus is placed on bus routing, while the groups determined during the routing process are not treated as a research subject. This approach can result in groups with a high density of nets, posing new challenges for practical routing. In response to this, a group routing algorithm based on a weighted directed graph is proposed in this paper. A Hanan grid graph is constructed, containing only merged edges and their adjacent relationships. Following this, a weighted directed graph is developed using the merged edge information to represent the routing resources on the circuit board. For routing planning, a heuristic search algorithm equipped with multi-wire avoidance features is utilized. The routing situations are then classified into several potential scenarios, each considered separately, to accomplish detailed routing and obtain the final result of group routing. Results from experiments demonstrate that a 100% routability is consistently achieved by the algorithm on complex industrial examples that have been previously tested, and that the design rule constraints of all benchmark industrial printed circuit board cases are not violated.