Using Reinforcement Learning to Optimize the Global and Local Crossing Number
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909775496740864 |
|---|---|
| author | Brand, Timo Förster, Henry Kobourov, Stephen Schukrafft, Robin Wallinger, Markus Zink, Johannes |
| author_facet | Brand, Timo Förster, Henry Kobourov, Stephen Schukrafft, Robin Wallinger, Markus Zink, Johannes |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06108 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Using Reinforcement Learning to Optimize the Global and Local Crossing Number Brand, Timo Förster, Henry Kobourov, Stephen Schukrafft, Robin Wallinger, Markus Zink, Johannes Computational Geometry Machine Learning 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. |
| title | Using Reinforcement Learning to Optimize the Global and Local Crossing Number |
| topic | Computational Geometry Machine Learning |
| url | https://arxiv.org/abs/2509.06108 |