Using Reinforcement Learning to Optimize the Global and Local Crossing Number

Timo Brand, Henry Förster, Stephen Kobourov, Robin Schukrafft, Markus Wallinger +1 more
9/7/2025
cs.CGcs.LG

No official code found. Best implementation: j-zink-wuerzburg/rl-4-gd-crossing-reduction (1 star, MIT, last commit 2025-09-20).

Abstract

We present a novel approach to graph drawing based on reinforcement learning for minimizing the global and the local crossing number, that is, the total number of edge crossings and the maximum number of crossings on any edge, respectively. In our framework, an agent learns how to move a vertex based on a given observation vector in order to optimize its position. The agent receives feedback in the form of local reward signals tied to crossing reduction. To generate an initial layout, we use a stress-based graph-drawing algorithm. We compare our method against force- and stress-based (baseline) algorithms as well as three established algorithms for global crossing minimization on a suite of benchmark graphs. The experiments show mixed results: our current algorithm is mainly competitive for the local crossing number. We see a potential for further development of the approach in the future.

View on arXivView PDF

Code Implementations(1)

j-zink-wuerzburg/rl-4-gd-crossing-reductionCommunity64%
MIT

Repository providing code and data for the paper "Using Reinforcement Learning to Optimize the Global and Local Crossing Number" by Timo Brand, Henry Förster, Stephen Kobourov, Robin Schukrafft, Markus Wallinger, and Johannes Zink

11C++, ShellSep 7, 20251 years agoMIT

Similar Papers

Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective

81% match2024

Graph Reinforcement Learning for Network Control via Bi-Level Optimization

81% match1 repo162023

RELIEF: Reinforcement Learning Empowered Graph Feature Prompt Tuning

80% match1 repo132024

Graph Drawing by Stochastic Gradient Descent

80% match1 repo502017

Learning and Editing Universal Graph Prompt Tuning via Reinforcement Learning

79% match1 repo82025

Collaborative Multi-Agent Reinforcement Learning for Automated Feature Transformation with Graph-Driven Path Optimization

78% match2025

Cite this paper

@article{brand2025using,
  title  = {Using Reinforcement Learning to Optimize the Global and Local Crossing Number},
  author = {Timo Brand and Henry Förster and Stephen Kobourov and Robin Schukrafft and Markus Wallinger and Johannes Zink},
  year   = {2025},
  eprint = {2509.06108},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2509.06108v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2509.06108.svg)](https://codeofpaper.com/paper/2509.06108)

Discussion