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 %
References
radioelektronnykh sredstv [Automation of design of radio-electronic means]. Moscow:
Vysshaya shkola, 2000, 479 p.
2. Gorbatov V.A. Fundamental'nye osnovy diskretnoy matematiki. Informatsionnaya matematika
[Fundamental foundations of discrete mathematics. Information Mathematics]. Moscow:
Nauka, Fizmatlit, 2000, 544 p.
3. Gorbatov V.A., Smirnov M.I., Khlytchiev I.S. Logicheskoe upravlenie raspredelennymi
sistemami [Logical management of distributed systems]. Moscow: Energoatomizdat, 1991,
287 p.
4. Shein A.B, Lazareva N.M. Metody proektirovaniya elektronnykh ustroystv [Design methods
for electronic devices]. Moscow: Infra-inzheneriya, 2011, 456 p.
5. Muromtsev D.Yu., Tyurin I.V., Belousov O.A., Kurnosov R.Yu. Proektirovanie funktsional'nykh
uzlov i moduley radioelektronnykh sredstv [Design of functional units and modules of radioelectronic
means]. Saint Petersburg: Lan', 2018, 251 p.
6. Berzh K. Teoriya grafov i ee primenenie [Graph theory and its application]. Moscow:
Inostrannaya literatura, 1962, 320 p.
7. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Computer-aided design basics].
Moscow: MGTU im. Baumana, 2009, 430 p.
8. Yurkov N.K. Tekhnologiya radioelektronnykh sredstv [The technology of radio electronic
means]. Penza: PGU, 2012, 640 p.
9. Gladkov L.A., Kureychik V.V., Kureychik V.M. Diskretnaya matematika [Discrete Mathematics].
Moscow: Fizmatlit, 2014, 496 p.
10. Kureychik V.M., Lebedev O.B., Lebedev B.K. Poiskovaya adaptatsiya [Search adaptation].
Moscow: Fizmatlit, 2006, 270 p.
11. Petrov Yu.V. Metody matematicheskogo modelirovaniya radiotekhnicheskikh system
[Methods of mathematical modeling of radio engineering systems]. Saint Petersburg: Balt. gos.
tekhn. un-t, 2005, 111 p.
12. Pirogova E.V. Proektirovanie i tekhnologiya pechatnykh plat [Design and technology of printed
circuit boards]. Moscow: Forum, 2005, 559 p.
13. Muromtsev Yu.L., Muromtsev D.Yu., Tyurin I.V. Informatsionnye tekhnologii proektirovaniya
radioelektronnykh sredstv [Information technologies for designing radio-electronic equipment].
Moscow: Akademiya, 2010, 384 p.
14. Potapov V.I., Suskin V.V., Shevchenko V.F. Teoriya kharakterizatsionnogo upravleniya v
konstruirovanii ploskikh struktur radioelektronnykh sredstv [Theory of characterization control in
the design of flat structures of radioelectronic devices]. Ryazan': OOO «Eko-tekst», 2017, 92 p.
15. Potapov V.I., Suskin V.V. Ob odnom podkhode k sintezu ploskikh struktur elektronnykh
sredstv s zhestkoy logikoy funktsionirovaniya [About one approach to the synthesis of planar
structures of electronic devices with function of rigid logic], Vestnik Ryazanskogo
gosudarstvennogo radiotekhnicheskogo universiteta [Bulletin of the Ryazan State Radio Engineering
University], 2016, No. 56, pp. 83-89.
16. Potapov V.I., Suskin V.V. Modeli i algoritmy proektirovaniya ploskikh struktur elektronnykh
sredstv na osnove gibkoy elementnoy baze [Models and algorithms for designing flat structures
of electronic devices based on a flexible element base], Vestnik Ryazanskogo
gosudarstvennogo radiotekhnicheskogo universiteta [Bulletin of the Ryazan State Radio Engineering
University], 2017, No. 62, pp. 79-88.
17. Potapov V.I. Zadacha sinteza struktury elektronnykh moduley, postroennykh s ispol'zovaniem
printsipov kharakterizatsionnogo upravleniya [The task of synthesizing the structure of electronic
modules built using the principles of characterization management], Sb. statey
Vserossiyskoy nauchno-prakticheskoy konferentsii «Strategiya nauchno-tekhnologicheskogo
razvitiya Rossii: problemy i perspektivy realizatsii. MTSNP «Novaya nauka» [Collection of articles
of the all-russian scientific and practical conference " strategy of scientific and technological
development of Russia: problems and prospects of implementation. MCNP "New science"].
Petrozavodsk, 2020, pp. 18-30.
18. Potapov V.I., Suskin V.V., Filatkin S.V. Printsip postroeniya ploskikh konstruktsiy
elektronnykh skhem s uchetom zapreshchennykh figur [The principle of constructing flat
structures of electronic circuits taking into account forbidden figures], IOP Conference Series:
Materials Science and Engineering (MSE), 2020.
19. Potapov V.I. Zapreshchennye figury v proektirovanii konstruktsiy elektronnykh moduley
[Prohibited figures in the design of electronic module structures], XXV Yubileynaya
Vserossiyskaya nauchno-tekhnicheskaya konferentsiya studentov, molodykh uchenykh i
spetsialistov «Novye informatsionnye tekhnologii v nauchnykh issledovaniyakh (NIT-2020):
Tez. dokl. Ryazan. gos. radiotekhn. un-t. Ryazan', 2020 [XXV Anniversary All-Russian Scientific
and Technical Conference of Students, Young Scientists and Specialists " New Information
Technologies in Scientific Research (NIT-2020): Abstracts of reports of the Ryazan
State Radio Engineering University. Ryazan, 2020].
20. Gumennikova A.V., Emel'yanova M.N., Semenkin E.S., Sopov E.A. Ob evolyutsionnykh
algoritmakh resheniya slozhnykh zadach optimizatsii [On evolutionary algorithms for solving
complex optimization problems], Vestnik SibGAU [Vestnik. SibGAU], 2003, No. 4, pp. 14-23.
21. Onishchenko T.Yu, Marasanov V.V. Kharakterizatsionnyy analiz kak optimizatsionnyy metod
kontrolya i prognozirovanie rabotosposobnosti elektronnykh skhem [Characterization analysis
as an optimization method for monitoring and predicting the performance of electronic circuits],
Vestnik KhNTU [Vestnik HNTU], 2013, No. 3, pp. 12-19.
