2026-07-24T11:33:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25042 2026-02-09T07:54:04Z ddc:004 open_access

Using Reinforcement Learning to Optimize the Global and Local Crossing Number (Poster Abstract) Brand, Timo Förster, Henry Kobourov, Stephen Schukrafft, Robin Wallinger, Markus Zink, Johannes Reinforcement Learning Crossing Minimization Local Crossing Number 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. An agent learns how to move a vertex based on a given observation vector. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timo Brand and Henry Förster and Stephen Kobourov and Robin Schukrafft and Markus Wallinger and Johannes Zink 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.56 urn:nbn:de:0030-drops-250420 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.56 eng https://creativecommons.org/licenses/by/4.0/legalcode