Home
Authors Papers Year of conference Themes Organizations To MES conference
A Method for Selecting an Isomorphic Subgraph of a Circuit Diagram Graph in Electronic Circuit CAD Systems 




Authors 
 Kurapov S.V. 
 Davidovsky M.V. 
Date of publication 
 2021 
DOI 
 10.31114/20787707202131825 

Abstract 
 Studying the properties of objects based on the analysis of their structural characteristics constitute one of the most important and promising directions in the development of applied graph theory. In general, discrete graph models represent the structures of objects of a very different nature. Analysis of structural characteristics of the designed objects becomes notably important in the design of microcircuits, printed circuit boards, flexible printed circuit boards, integrated circuits, as well as LSI, VLSI and other flat constructs design processes. Thus, a challenging task within the scope of modern CAD systems development activities is the problem of recognizing the structures of various designed objects. In order to increase the efficiency of CAD, in practice, there is a need to use graph isomorphism testing – for example, to verify various representations of an electronic circuit when automating electronic circuits design. The article is devoted to applied mathematical methods for determining the isomorphism of subgraphs of circuit diagram graphs in electronic equipment CAD systems. In this work the authors present a method for solving the problem of extracting a subgraph G0 from graph G(V,E), which is isomorphic to a given reference graph H(X,U). The method is based on the use of a complete invariant of a graph representing its individual structure in numerical form. Preliminary determination of the complete invariant for the reference graph allows reducing the problem to finding a set of subgraphs of the graph G with the number of vertices equal to the cardinality card(X) of the set of vertices of the graph H. The proposed solution consists in enumerating all sets of Xcombinations fromV. Such a problem statement allows applying computational methods with polynomial computational complexity to solve the original hard problem. 
Keywords 
 computeraided design system, electrical schematic diagram graph, graph isomorphism, isomorphic subgraph extraction. 
Library reference 
 Kurapov S.V., Davidovsky M.V. A Method for Selecting an Isomorphic Subgraph of a Circuit Diagram Graph in Electronic Circuit CAD Systems // Problems of Perspective Micro and Nanoelectronic Systems Development  2021. Issue 3. P. 1825. doi:10.31114/20787707202131825 
URL of paper 
 http://www.mesconference.ru/data/year2021/pdf/D065.pdf 

