A new neural network algorithm for planarization problems  

作　　者：ZHANG JunYing QIN Qiang 

机构地区：[1]School of Computer Science and Engineering, Xidian University, Xi'an 710071, China

出　　处：《Science in China(Series F)》2008年第12期1947-1957,共11页中国科学（F辑英文版）

基　　金：the Sino-Italy Joint Cooperation Project;the National Visiting Scholar fund of China

摘　　要：To deal with the planarization problem widely used in many applications including routing very-large-scale integration （VLSI） circuits, this paper points out that only when its vertices are arranged in some specific order in a line can a planar graph be embedded on a line without any cross connections or cross edges. Energy function is proposed to meet the need of embedding a graph on a single line and route it correctly. A Hopfield network is designed according to the proposed energy function for such embedding and routing. The advantage of the proposed method is that it not only can detect if a graph is a planar one or not, but also can embed a planar graph or the maximal planar subgraph of a non-planar graph on a single line. In addition, simulated annealing is employed for helping the network to escape from local minima during the running of the Hopfield network. Experiments of the proposed method and its comparison with some existent conventional methods were performed and the results indicate that the proposed method is of great feasibility and effectiveness especially for the planarization problem of large graphs.To deal with the planarization problem widely used in many applications including routing very-large-scale integration （VLSI） circuits, this paper points out that only when its vertices are arranged in some specific order in a line can a planar graph be embedded on a line without any cross connections or cross edges. Energy function is proposed to meet the need of embedding a graph on a single line and route it correctly. A Hopfield network is designed according to the proposed energy function for such embedding and routing. The advantage of the proposed method is that it not only can detect if a graph is a planar one or not, but also can embed a planar graph or the maximal planar subgraph of a non-planar graph on a single line. In addition, simulated annealing is employed for helping the network to escape from local minima during the running of the Hopfield network. Experiments of the proposed method and its comparison with some existent conventional methods were performed and the results indicate that the proposed method is of great feasibility and effectiveness especially for the planarization problem of large graphs.

关 键 词：graph planarization problem planar embedding algorithm Hopfield network energy function SIMULATEDANNEALING 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]