Crossing Minimization for Bi-Partite Graphs (Research & Documentation)

Abstract

We focus on the Bi-partite graph crossing minimization problem by implementing different heuristics, namely Minsort, Minsort*, Barycenter and Median that have been discussed in [1] and compare these techniques by running the simulations on different datasets. Bipartite graphs have many applications in real life. Sparse Bi-partite graphs are generated randomly for each simulation, but there are different input parameters for each simulation that let us analyse the performance of these heuristics order. All of these techniques are then compared with each other along with the help of the simul.ations results . Cuts minimization is an area of interest for a lot of people in different fields and many techniques are available for cuts minimization