A Greedy Heuristic for Crossing-Angle Maximization

Abstract

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{N}P$-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.

Appears in the Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018)