Minimizing Edge Crossing in Drawing Bipartite Graphs Using Evolutionary Algorithm

摘要

This paper introduces an evolutionary algorithm (EA) for the bipartite drawing problem (BDP). A graph G is bipartite if V(G) can be partitioned into two (nonempty) subsets V_1 and V_2 such that every edge of G joins a vertex of V_1 and a vertex of V_2. The problem aims to adjust the drawing to minimize the number of edge crossings. The performance of the commonly employed barycenter heuristic (BC) is compared to EA approach. In any optimization process, the goal is to find the best solution. For small spaces, classical exhaustive search methods usually suffice. For larger spaces, special artificial intelligence techniques must be employed. EA models natural selection which generates new points in the search by applying operators to current points and statistically moving toward more optimal points in the search space. Graphs are used to represent aspects of systems in a wide variety of disciplines, including software, networking, information engineering, management and desktop publishing. The usefulness of these representations depends on the layout of the graph. Thus, there has been considerable interest in algorithms for drawing directed graphs to make them easier to understand and remember.