# Using Reinforcement Learning to Optimize the Global and Local Crossing Number

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 7 Sep 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 17 of 17)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [A Deep Generative Model for Graph Layout](https://mlsanity.com/paper/1904.12225/) (2019)
- [DeepDrawing: A Deep Learning Approach to Graph Drawing](https://mlsanity.com/paper/1907.11040/) (2019)
- [DeepGD: A Deep Learning Framework for Graph Drawing Using GNN](https://mlsanity.com/paper/2106.15347/) (2021)
- [Deep Neural Network for DrawiNg Networks, (DNN)^2](https://mlsanity.com/paper/2108.03632/) (2021)
- [SmartGD: A GAN-Based Graph Drawing Framework for Diverse Aesthetic Goals](https://mlsanity.com/paper/2206.06434/) (2022)
- [A Heuristic Approach towards Drawings of Graphs with High Crossing Resolution](https://mlsanity.com/paper/1808.10519/) (2018)
- [A Survey on Graph Drawing Beyond Planarity](https://mlsanity.com/paper/1804.07257/) (2018)
- [Stress-Plus-X (SPX) Graph Layout](https://mlsanity.com/paper/1908.01769/) (2019)
- [An annotated bibliography on 1-planarity](https://mlsanity.com/paper/1703.02261/) (2017)
- [A Greedy Heuristic for Crossing-Angle Maximization](https://mlsanity.com/paper/1807.09483/) (2018)
- [Interpreting Graph Drawing with Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2011.00748/) (2020)

## Abstract (arXiv)

Graph drawing concerns the algorithmic visualization of graphs. A good drawing of a graph is easy to read and facilitates solving tasks on the graph. Several properties have been identified to occur in good drawings of graphs. Such properties include a low number of crossings, large angles between edges, short edges, and depicting symmetries. Many of these properties are explicitly measurable metrics. This lets us model a graph-drawing problem as a game where a single player iteratively moves vertices of a straight-line graph drawing to reduce edge crossings. We investigate whether reinforcement learning can discover effective strategies for playing this game. Our reinforcement-learning agent observes the local geometric and structural context of a vertex and selects a movement direction with the goal of reducing either the global or the local crossing number, that is, either the total number of crossings or the maximum number of crossings per edge. We compare the resulting strategies to existing methods and established crossing-minimization heuristics on standard benchmark graphs. While our approach does not out-compete state-of-the-art methods for minimizing the global crossing number, it is competitive and often superior for minimizing the local crossing number.