DROPS

Document

Graph Drawing Contest Abstract

DOI: 10.4230/LIPIcs.GD.2025.43

Winning the GD Challenge for the 4th Time: Our Approach (Graph Drawing Contest Abstract)

Authors: Julien Bianchetti and Laurent Moalic

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

Abstract

We present the approach we designed to tackle and win the 2025 Graph Drawing Challenge on minimizing the k-planarity of graphs. Our method employs a multi-stage heuristic centered around two Simulated Annealing (SA) algorithms: the first aims to reduce the total number of crossings, while the second improves the k-value. To obtain a good initial solution, we first applied tools from the OGDF library, which helped reduce crossings. The challenge consisted of nine instances to optimize. Our approach achieved the best results on eight out of nine instances - sharing the top score twice with other teams and ranking first alone in six cases.

Cite as

Julien Bianchetti and Laurent Moalic. Winning the GD Challenge for the 4th Time: Our Approach (Graph Drawing Contest Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 43:1-43:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bianchetti_et_al:LIPIcs.GD.2025.43,
  author =	{Bianchetti, Julien and Moalic, Laurent},
  title =	{{Winning the GD Challenge for the 4th Time: Our Approach}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{43:1--43: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.43},
  URN =		{urn:nbn:de:0030-drops-250293},
  doi =		{10.4230/LIPIcs.GD.2025.43},
  annote =	{Keywords: Graph Drawing Contest, simulated annealing, k-planarity}
}

Search Results

Documents authored by Bianchetti, Julien

Winning the GD Challenge for the 4th Time: Our Approach (Graph Drawing Contest Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message