Crossing Minimization in Bipartite Graphs

Abstract

Since pre-Newtonian times, graphs have been used to show connections between things. Technically, a graph is a set of vertices, some pairs of which are connected. This leads to many applications and has led to a significant body of research. Some of the applications of graphs include map coloring, travel optimization, games of strategy, and the use of networks to solve traffic flow problems. There are different conventions for drawing graphs. One of these conventions is a planar graph, which is a graph that can be drawn in the plane so that edges can meet only at vertices. A bipartite graph is a type of planar graphs, which has two different sets of vertices and where one set of vertices cannot be joined to the other in the same set but are joined with vertices from the opposite set. This results in crossings between the edges. There are different heuristics / algorithms that have been developed for reducing the crossings. The performance of these heuristics is one of the major aspects that are discussed in this document. The focus is on the bipartite graph crossing minimization problem by implementing different heuristics, namely Minsort, Minsort*, Barycenter and Median and compare these techniques by running the simulations on different datasets. Sparse bipartite graphs are generated randomly for each simulation, but there are different input parameters for each simulation that let us analyze the performance of these heuristics order. All of these techniques are then compared with each other along with the help of the simulation results. Crossing minimization is an area of interest for a lot of people in different fields and many techniques are available for this purpose. Cluster detection in bipartite graphs is presented using the Quadrature Technique. The Quadrature Technique is a recursive procedure that works by first applying a crossing minimization heuristic on the input graph, then splitting this resulting graph into four quadrants and applying the heuristic on the data quadrants (quadrants along the diagonal) ignoring the edges in the noise quadrants and continuing this recursive splitting for each data quadrant until a stopping condition is reached. The performance of each heuristic was the main area of research and the results showed that the Barycenter Heuristic proved to be the best in reducing crossing 2 Bipartite Graph Crossing Minimization 3 minimization. This justified the theoretical results that were obtained from the literature survey that Barycenter is the most efficient heuristic for cuts minimization problem.