Search

Search Results

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

  V. I. Potapov

  2021-01-19

  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 %