Incremental bipartite drawing problem

Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossin g minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the o ptimal solution of the GRASP approach. Computational experiments are perfor med with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure .