APPLICATION OF FORBIDDEN SHAPES IN THE GRAPH COLORING PROBLEM WHEN DESIGNING PRINTED CIRCUIT BOARDS
Keywords:
Flat structure of electronic means, graph-theoretical approach, prohibited figures, trace in a single layer, graph, an edge of the graph, planarity prohibited figure, algorithm, analysis, synthesis, electric radio elementAbstract
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 %
