EDGE CROSSINGS IN DRAWINGS OF BIPARTITE GRAPHS

Systems engineers have recently shown interest in algorithms for drawi ng directed graphs so that they are easy to understand and remember. E ach of the commonly used methods has a step which aims to adjust the d rawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimiz ation of the number of arcs in crossings in a bipartite graph. The per formance of the commonly employed ''barycenter'' heuristic for this pr oblem is analyzed. An alternative method, the ''median'' heuristic, is proposed and analyzed. The new method is shown to compare favorably w ith the old in terms of performance guarantees. As a bonus, we show th at the median heuristic performs well with regard to the total length of the arcs in the drawing.