mlsanityData to 14 Oct 2026

Using Reinforcement Learning to Optimize the Global and Local Crossing Number

arXiv 2509.06108 ↗First posted 7 Sep 2025cs.CG cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

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.

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.

Builds on

17 of 56 references.

References · 17

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2017Graph Attention Networkscited by 8,923
  3. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  4. 2018Deep Graph Infomaxcited by 1,106
  5. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  6. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 186
  7. 2019A Deep Generative Model for Graph Layoutcited by 19
  8. 2019DeepDrawing: A Deep Learning Approach to Graph Drawingcited by 15
  9. 2021DeepGD: A Deep Learning Framework for Graph Drawing Using GNNcited by 10
  10. 2021Deep Neural Network for DrawiNg Networks, (DNN)^2cited by 6
  11. 2022SmartGD: A GAN-Based Graph Drawing Framework for Diverse Aesthetic Goalscited by 6
  12. 2018A Heuristic Approach towards Drawings of Graphs with High Crossing Resolutioncited by 4
5 more
  1. 2018A Survey on Graph Drawing Beyond Planaritycited by 3
  2. 2019Stress-Plus-X (SPX) Graph Layoutcited by 3
  3. 2017An annotated bibliography on 1-planaritycited by 1
  4. 2018A Greedy Heuristic for Crossing-Angle Maximizationcited by 1
  5. 2020Interpreting Graph Drawing with Multi-Agent Reinforcement Learningcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  2. 2024G-PCGRL: Procedural Graph Data Generation via Reinforcement Learning
  3. 2025An Efficient Hybridization of Graph Representation Learning and Metaheuristics for the Constrained Incremental Graph Drawing Problem
  4. 2026RLGT: A reinforcement learning framework for extremal graph theory
  5. 2025Reinforcement learning for graph theory, Parallelizing Wagner's approach
  6. 2025Reinforcement Learning for Game-Theoretic Resource Allocation on Graphs
  7. 2026PlanarBench: Evaluating LLM Spatial Reasoning via Planar Graph Drawing
  8. 2025RIDGECUT: Learning Graph Partitioning with Rings and Wedges