Algorithm of Graph Planarity Defenition for Improving the Quality of the Very Large Scale Integrations Circuits Tracking

摘要

Locating graph vertices on a plane problem is considered in this paper. This problem is directly related to the engineering problem arising in a very large-scale integrated circuits topology design. This task is relevant because it determines such important indicators as the quality of design engineering and the cost of very large-scale integrated circuits production. It includes a certain set of modules placement on a plane, as well as the chains that must connect the designed crystal’s modules. The topologic drawing is required to obtain a flat image of the scheme or its parts. In this regard, the projected scheme is often represented as a graph model, which vertices correspond to the designed very large integrated circuits modules, and the edges - to the modules connections. After graph construction, in practice designers often face another task - the planarity graph definition. If the graph is planar, then all the edges can be positioned on a plane, respectively, and all the projected scheme connections can be placed on one projected crystal layer. If the graph is not planar, then some connections of the scheme are transferred on the other layers.This paper considers the algorithm for determining the graph planarity. The novelty of this approach lies in the fact of quantum algorithm and the genetic search algorithm hybridization. There are fairly simple algorithms of graph planarity definition, if it contains a Hamiltonian cycle. However, the task of finding the Hamiltonian cycle in the graph is NP hard. In this regard, the work proposed a quantum search algorithm for finding the Hamiltonian cycle in a graph, which is a modification of the Grover algorithm. The genetic search algorithm is used when the Hamiltonian cycle is not found in the graph. Since the genetic algorithm work quality strongly depends on the parameters choice, the proposed method fundamental difference is the use of special indicators to analyze the further use of the genetic algorithm operators in the evolutionary adaptation unit. Experimental results have shown developed method effectiveness for solving the classical problem of determining the graph planarity and reducing the total algorithm operating time, using special population degradation degree indicators.