Search Results

Documents authored by Brand, Timo

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