THE ASSIGNMENT HEURISTIC FOR CROSSING REDUCTION

Several applications use algorithms for drawing k-layered networks and , in particular, 2-layered networks (i.e., bipartite graphs). Bipartit e graphs are commonly drawn in the plane so that all vertices lie on t wo parallel vertical lines, and an important requirement in drawing su ch graphs is to minimize edge crossings. Such a problem is NP-complete even when the position of the vertices on one layer is held fixed. Th is paper presents a heuristic, called the assignment heuristic, for ed ge crossing minimization in bipartite graphs, which works by reducing the problem to an assignment problem. The main idea of the assignment heuristic is to position simultaneously all the vertices of one layer, so that the mutual interaction of the position of all the vertices ca n be taken into account. We also show that the idea underlying the ass ignment heuristic can be effectively applied in other cases requiring edge crossing minimization.