Solving a near-maximal graph planarization problem using strictly digital neural networks with virtual slack-neurons

This paper presents a neural network parallel algorithm for solving a near optimum graph planarization problems using SDNN/V (strictly digital neural networks enhanced with virtual slack-neurons). The proposed algorithm generates a near-maximal planar subgraph from a nonplanar or a planar graph within O(1) time. The problem can be defined as a “set selection problem” based on the “between-l-and-k-out-of-n” design rule in SDNN/V algorithm, The results of solving the graph planarization problem using a simulator of SDNN/V show that the computation in parallel execution is only three steps to get one of the near-optimum solutions. However, the obtained solutions are not always maximal subgraphs. In order to improve the quality of the solutions, this paper presents a numbering method for neurons in an order of importance within each constraint satisfaction set. From the result of simulation, it is shown that the numbering method has an effect on improving the quality of the solutions