Arc crossing minimization in hierarchical digraphs with tabu search

Arc crossing minimization in hierarchical digraphs with tabu search

0.00 Avg rating0 Votes
Article ID: iaor19981821
Country: United Kingdom
Volume: 24
Issue: 12
Start Page Number: 1175
End Page Number: 1186
Publication Date: Dec 1997
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

Graphs are used commonly as a basic modeling tool in areas such as project management, production scheduling, line balancing, business process reengineering, and software visualization. An important problem in the area of graph drawing is to minimize arc crossings in a multi-layer hierarchical digraph. Existing solution methods for this problem are based on simple ordering rules for single layers that may lead to inferior drawings. This article first introduces an extensive review of relevant work previously published in this area. Then a tabu search implementation is presented that seeks high-quality drawings by means of an intensification phase that finds a local optimum according to an insertion mechanism and two levels of diversification. Computational experiments with 200 graphs with up to 30 nodes per layer and up to 30 layers are presented to assess the merit of the method.

Reviews

Required fields are marked *. Your email address will not be published.