APPLICATION OF FORBIDDEN SHAPES IN THE GRAPH COLORING PROBLEM WHEN DESIGNING PRINTED CIRCUIT BOARDS

Abstract

Designing a printed circuit board in the form of flat structures without jumpers is one of the most difficult tasks at the stage of circuit design. The task in this formulation is especially relevant for micro-assemblies for electronic modules of control and verification, on-board equipment, made using surface-mount technology, where, for example, due to a metal heat sink or a ceramic base, the structure of connections is possible only in one layer. The paper deals with the problem of designing printed circuit boards in the form of synthesis of flat structures of electronic circuits. The goal is to position the connections on the PCB without overlapping, making it easier for any router in modern design programs to route. To solve it, a large number of different algorithms have been proposed, the main disadvantage of which is the principle of sequential and fragmentary viewing of the switching space inherent in them. The complexity of the algorithms for the synthesis of such structures is also due to the need to take into account a large number of different requirements associated with the specifics of their manufacture and the features of the developed constructive and technological solution. In this paper, it is proposed to design a printed circuit board with a high efficiency of routing connections by solving the problem of stratifying the original graph-scheme and constructing a flat graph-scheme both on the installation side of the electrical radio elements and on the reverse side of the board - the soldering side, excluding forbidden figures according to Potryagin's theorem - Kuratovsky. The criterion is to minimize vias as well as minimize conductors (fins) on one side of the PCB. The bundle problem is a graph coloring problem in two colors using the principles of characterization control, the solution of which is based on the Koenig theorem, which defines a forbidden figure in the form of cycles of odd length. For the design of printed circuit boards, an algorithm and method for constructing planar graphs and stratifying the graph into two sides of the printed circuit board with a decrease in the number of undistributed edges have been developed. The exact solution takes the form of a polynomial dependence not higher than the 5th degree, it allows you to get the result in a reasonable time and increase the tracing efficiency by 5–15 %