Planarization Of A Graph With A New Neural Network Algorithm

Planarization problem is a representative problem in Combination Optimization. It is widely used in designing printed circuit boards, routing very-large-scale integration (VLSI) circuits and very important to the visibility of the Gene Regulatory Network. The planarization problem consists of two parts: the planarization testing and the plane-embedding. Many algorithms about this problem have been proposed by many researchers but there exist bugs in them. To settle these two sub-problems, a new Hopfield network algorithm is proposed. This paper points out that the planar graph can only be embedded onto a single line when its vertices are in special order. It also presents an energy function that can meet the need of embedding a graph onto a single line and routing the graph correctly. Then a Hopfield neural network is applied for decreasing the energy of the network with respect of time, such that we can not only generate a maximal planar subgraph from a nonplanar graph or a planar graph but also embed the subgraph onto a single line. In addition, simulated annealing algorithm was used to help the network escape from the local minima. Plenty of experimental results have proved that our hybrid algorithm has the ability to help Hopfield network escape from local minima and get better results.