DROPS

Document

DOI: 10.4230/LIPIcs.GD.2026.24

Using Reinforcement Learning to Optimize the Global and Local Crossing Number

Authors: Timo Brand, Henry Förster, Stephen Kobourov, Daniel Kohrt, Robin Schukrafft, Markus Wallinger, and Johannes Zink

Published in: LIPIcs, Volume 396, 34th International Symposium on Graph Drawing and Network Visualization (GD 2026)

Abstract

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.

Cite as

Timo Brand, Henry Förster, Stephen Kobourov, Daniel Kohrt, Robin Schukrafft, Markus Wallinger, and Johannes Zink. Using Reinforcement Learning to Optimize the Global and Local Crossing Number. In 34th International Symposium on Graph Drawing and Network Visualization (GD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 396, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brand_et_al:LIPIcs.GD.2026.24,
  author =	{Brand, Timo and F\"{o}rster, Henry and Kobourov, Stephen and Kohrt, Daniel and Schukrafft, Robin and Wallinger, Markus and Zink, Johannes},
  title =	{{Using Reinforcement Learning to Optimize the Global and Local Crossing Number}},
  booktitle =	{34th International Symposium on Graph Drawing and Network Visualization (GD 2026)},
  pages =	{24:1--24:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-452-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{396},
  editor =	{L\"{o}ffler, Maarten and Miksch, Silvia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2026.24},
  URN =		{urn:nbn:de:0030-drops-279193},
  doi =		{10.4230/LIPIcs.GD.2026.24},
  annote =	{Keywords: Reinforcement Learning, Crossing Minimization, Local Crossing Number}
}

Search Results

Documents authored by Kohrt, Daniel

Using Reinforcement Learning to Optimize the Global and Local Crossing Number

Abstract

Cite as

Thanks for your feedback!

Could not send message