An_improved_neural_network_model_for_the_2-page_crossing_number_problem.pdf (285.43 kB)

Download file# An improved neural network model for the two-page crossing number problem

journal contribution

posted on 2006-09-25, 13:39 authored by Hongmei He, Ondrej Sykora, Erkki MakinenThe simplest graph drawing method is that of putting the vertices of a graph on a line and
drawing the edges as half-circles either above or below the line. Such drawings are called 2-page book drawings. The smallest number of crossings over all 2-page drawings of a graph G is called the 2-page crossing number of G. Cimikowski and Shope have solved the 2-page crossing number problem for an n-vertex and
m-edge graph by using a Hopfield network with 2m
neurons. We present here an improved Hopfield modelwith m neurons. The new model achieves much better performance in the quality of solutions and is more efficient than the model of Cimikowski and Shope for all graphs tested. The parallel time complexity of the algorithm, without considering the crossing number
calculations, is O(m), for the new Hopfield model with m processors clearly outperforming the previous algorithm.

## History

## School

- Science

## Department

- Computer Science