# A Greedy Heuristic for Crossing-Angle Maximization

arXiv: https://arxiv.org/abs/1807.09483 · HTML: https://mlsanity.com/paper/1807.09483/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [Using Reinforcement Learning to Optimize the Global and Local Crossing Number](https://mlsanity.com/paper/2509.06108/) (2025)

## Abstract (arXiv)

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.