Search Results

Documents authored by Brand, Timo

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}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2026.44
Toroidal Graph Drawing by Multidimensional Scaling (Poster Abstract)

Authors: Timo Brand, Sebastian Damrich, Stephen Kobourov, and Jacob Miller

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

Abstract
We present a framework for multidimensional scaling of graph data to the flat torus. Compared to prior approaches, we contribute a closed-form geodesic distance computation, and learnable parameters for the torus size and aspect ratio, with an extension to rhombic tori. On synthetic benchmarks, our layouts achieve lower normalized stress than Euclidean baselines, and on real toroidal data our method recovers the underlying structure.
Cite as

Timo Brand, Sebastian Damrich, Stephen Kobourov, and Jacob Miller. Toroidal Graph Drawing by Multidimensional Scaling (Poster Abstract). In 34th International Symposium on Graph Drawing and Network Visualization (GD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 396, pp. 44:1-44:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brand_et_al:LIPIcs.GD.2026.44,
  author =	{Brand, Timo and Damrich, Sebastian and Kobourov, Stephen and Miller, Jacob},
  title =	{{Toroidal Graph Drawing by Multidimensional Scaling}},
  booktitle =	{34th International Symposium on Graph Drawing and Network Visualization (GD 2026)},
  pages =	{44:1--44:5},
  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.44},
  URN =		{urn:nbn:de:0030-drops-279393},
  doi =		{10.4230/LIPIcs.GD.2026.44},
  annote =	{Keywords: Graph layout, non-Euclidean geometry, multidimensional scaling}
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.28
Rerouting Curves on Surfaces

Authors: Timo Brand, Stefan Felsner, Henry Förster, Stephen Kobourov, Anna Lubiw, Yoshio Okamoto, János Pach, Csaba D. Tóth, Géza Tóth, Torsten Ueckerdt, and Pavel Valtr

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
We study the problem of reconfiguring a crossing-free embedding of a graph on a surface, with edges represented as curves, into another crossing-free embedding of the same graph on the same surface with the same fixed vertex positions. In this process, we reroute one edge at a time while maintaining crossing-free intermediate embeddings. This problem was introduced by Ito et al. [TALG 2025], who showed that even if the graph is a matching of two edges, reconfiguration is not always possible in the plane, but is always possible on the torus. For matchings of two or more edges, they gave a necessary and sufficient condition for reconfigurable embeddings in the plane, but not on the torus. Our main result is that for matchings, trees and forests, reconfiguration is always possible on the torus, and consequently, on any orientable surface of genus at least one. In addition, we provide sufficient conditions for reconfiguration on orientable surfaces of genus at least one and in the projective plane. For more general graphs, we show that reconfiguration is not always possible.
Cite as

Timo Brand, Stefan Felsner, Henry Förster, Stephen Kobourov, Anna Lubiw, Yoshio Okamoto, János Pach, Csaba D. Tóth, Géza Tóth, Torsten Ueckerdt, and Pavel Valtr. Rerouting Curves on Surfaces. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brand_et_al:LIPIcs.ESA.2026.28,
  author =	{Brand, Timo and Felsner, Stefan and F\"{o}rster, Henry and Kobourov, Stephen and Lubiw, Anna and Okamoto, Yoshio and Pach, J\'{a}nos and T\'{o}th, Csaba D. and T\'{o}th, G\'{e}za and Ueckerdt, Torsten and Valtr, Pavel},
  title =	{{Rerouting Curves on Surfaces}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.28},
  URN =		{urn:nbn:de:0030-drops-271641},
  doi =		{10.4230/LIPIcs.ESA.2026.28},
  annote =	{Keywords: Combinatorial reconfiguration, orientable surface, non-orientable surface, rerouting}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.56
Using Reinforcement Learning to Optimize the Global and Local Crossing Number (Poster Abstract)

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

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

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. 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.
Cite as

Timo Brand, Henry Förster, Stephen Kobourov, Robin Schukrafft, Markus Wallinger, and Johannes Zink. Using Reinforcement Learning to Optimize the Global and Local Crossing Number (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 56:1-56:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brand_et_al:LIPIcs.GD.2025.56,
  author =	{Brand, Timo and F\"{o}rster, Henry and Kobourov, Stephen and Schukrafft, Robin and Wallinger, Markus and Zink, Johannes},
  title =	{{Using Reinforcement Learning to Optimize the Global and Local Crossing Number}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{56:1--56:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.56},
  URN =		{urn:nbn:de:0030-drops-250420},
  doi =		{10.4230/LIPIcs.GD.2025.56},
  annote =	{Keywords: Reinforcement Learning, Crossing Minimization, Local Crossing Number}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact