TY - GEN
T1 - A solution to bipartite drawing problem using genetic algorithm
AU - Khan, Salabat
AU - Bilal, Mohsin
AU - Sharif, Muhammad
AU - Khan, Farrukh Aslam
PY - 2011
Y1 - 2011
N2 - Crossing minimization problem in a bipartite graph is a well-known NP-Complete problem. Drawing the directed/undirected graphs such that they are easy to understand and remember requires some drawing aesthetics and crossing minimization is one of them. In this paper, we investigate an intelligent evolutionary technique i.e. Genetic Algorithm (GA) for bipartite drawing problem (BDP). Two techniques GA1 and GA2 are proposed based on Genetic Algorithm. It is shown that these techniques outperform previously known heuristics e.g., MinSort (M-Sort) and BaryCenter (BC) as well as a genetic algorithm based level permutation problem (LPP), especially when applied to low density graphs. The solution is tested over various parameter values of genetic bipartite drawing problem. Experimental results show the promising capability of the proposed solution over previously known heuristics.
AB - Crossing minimization problem in a bipartite graph is a well-known NP-Complete problem. Drawing the directed/undirected graphs such that they are easy to understand and remember requires some drawing aesthetics and crossing minimization is one of them. In this paper, we investigate an intelligent evolutionary technique i.e. Genetic Algorithm (GA) for bipartite drawing problem (BDP). Two techniques GA1 and GA2 are proposed based on Genetic Algorithm. It is shown that these techniques outperform previously known heuristics e.g., MinSort (M-Sort) and BaryCenter (BC) as well as a genetic algorithm based level permutation problem (LPP), especially when applied to low density graphs. The solution is tested over various parameter values of genetic bipartite drawing problem. Experimental results show the promising capability of the proposed solution over previously known heuristics.
KW - Bipartite Drawing Problem (BDP)
KW - Bipartite Graph
KW - Crossing Minimization
KW - Crossing Minimization Heuristics (CMH)
KW - Genetic Algorithm
UR - http://www.scopus.com/inward/record.url?scp=79958213413&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-21515-5_63
DO - 10.1007/978-3-642-21515-5_63
M3 - Conference contribution
AN - SCOPUS:79958213413
SN - 9783642215148
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 530
EP - 538
BT - Advances in Swarm Intelligence - Second International Conference, ICSI 2011, Proceedings
T2 - 2nd International Conference on Swarm Intelligence, ICSI 2011
Y2 - 12 June 2011 through 15 June 2011
ER -