A neural-network algorithm for a graph layout problem

Author

Cimikowski, Robert ; Shope, Paul

Author_Institution

Dept. of Comput. Sci., Montana State Univ., Bozeman, MT, USA

Volume

7

Issue

2

fYear

1996

fDate

3/1/1996 12:00:00 AM

Firstpage

341

Lastpage

345

Abstract

We present a neural-network algorithm for minimizing edge crossings in drawings of nonplanar graphs. This is an important subproblem encountered in graph layout. The algorithm finds either the minimum number of crossings or an approximation thereof and also provides a linear embedding realizing the number of crossings found. The parallel time complexity of the algorithm is O(1) for a neural network with n² processing elements, where n is the number of vertices of the graph. We present results from testing a sequential simulator of the algorithm on a set of nonplanar graphs and compare its performance with the heuristic of Nicholson

Keywords

computational complexity; graph theory; mathematics computing; neural nets; optimisation; parallel algorithms; approximation; combinatorial optimisation; edge crossings; graph layout problem; neural-network; nonplanar graphs drawing; parallel algorithm; time complexity; Approximation algorithms; Biological system modeling; Computational modeling; Neural networks; Neurons; Printed circuits; Routing; Semiconductor device modeling; Very large scale integration; Wires;

fLanguage

English

Journal_Title

Neural Networks, IEEE Transactions on

Publisher

ieee

ISSN

1045-9227

Type

jour

DOI

10.1109/72.485670

Filename

485670