A Greedy Heuristic for Crossing-Angle Maximization

The crossing angle of a straight-line drawing Gamma of a graph G=(V, E) is the smallest angle between two crossing edges in Gamma. Deciding whether a graph G has a straight-line drawing with a crossing angle of 90^circ is mathcal NP-hard. We propose a simple heuristic to compute a drawing with a large crossing angle. The heuristic greedily selects the best position for a single vertex in a random set of points. The algorithm is accompanied by a speed-up technique to compute the crossing angle of a straight-line drawing. We show the effectiveness of the heuristic in an extensive empirical evaluation. Our heuristic was clearly the winning algorithm (CoffeeVM) in the Graph Drawing Challenge 2017.