An Efficient Parallel Algorithm for Two-layer Planarization in Graph Drawing

摘要

We present a parallel algorithm for the two-layer planarizatin problem using a grient ascent learning of Hopfield network. This algorithm which is designed to embed a two-layer graph on a plane, uses the hopfield network to get a near-maximal planar subgraph, and increases the energy by modifying weights in a gradient ascent direction to help the Hopfield network escape from the state of near-maximal planar subgraph to the state of the maximl planar subgraph. The experimental results show that the proposed algorithm can generate better solutions than the traditional Hopfield network.