Winning the GD Challenge for the 4th Time:
Our Approach

For this step, our goal was to quickly generate a high-quality initial layout. We utilized the powerful Open Graph Drawing Framework (OGDF) [2], which provides robust implementations of several layout algorithms. We specifically used Stress Minimization [4] and the Fast Multipole Multilevel Method (FMMM) [6, 5].

Stress Minimization is applied only once, since it is deterministic – that is, two runs produce exactly the same result. Then, we apply FMMM as many times as possible within the first minute. Because FMMM is stochastic, two runs yield different solutions.

At the end of the first minute, or after the time required for Stress Minimization (SM) and FMMM, we consider the best solution obtained so far among the initial solution (directly from the data file), the one from SM, and all the FMMM runs. Here, the best solution is defined as the one with the smallest $k$-value.

The 2023 and 2024 contest topics focused on minimizing the total number of edge crossings in a graph. Another difference was that nodes could only be placed at predefined positions (locations). It is quite clear that reducing the number of crossing edges is relevant in terms of $k$-planarity. Indeed, even though decreasing the number of crossings is not necessarily synonymous with decreasing the $k$-value, it generally provides significant improvement in most cases.

Algorithm 1 describes the key steps for reducing the total number of edge crossings.

$selectNode()$ and $selectPlace()$ play a significant role. $selectNode()$ is important because not all nodes have the same impact on the current $k$-value. If all edges originating from a given node have few crossings, moving that node will yield only a small improvement compared to moving a node connected to edges with many crossings. For this reason, nodes belonging to edges with many crossings are given a higher probability of being selected for movement.

$selectPlace()$ is also important. If the new position selected for a node is far from its previous location, there is a risk of creating many new crossings. For this reason, we decided to give a higher probability of selection to positions close to the node’s previous location.

A move is always accepted from $acceptMove()$ if it reduces or maintains the total number of crossings. A move that increases the crossings by $\mathrm{\Delta }C$ is accepted with a probability of $\exp (-\mathrm{\Delta }C/T_{current})$.

In this phase, we focus on optimizing the total number of crossings. However, it should be noted that each new wave starts from the best $k$-solution found so far. This is done to prepare for the final and main step of the proposed algorithm.

With the remaining time (at most 49 minutes), we switch to a second SA algorithm that directly optimizes the $k$-value. This phase uses the same structure as Algorithm 1 but employs a more sophisticated fitness function for the $acceptMove()$ criterion:

1. 1.

   Primary Objective: Local k-value Improvement. A move is evaluated based on the change in the maximum number of crossings on any edge involved in the move (i.e., edges incident to the moved node and edges that cross them). This local computation is much faster than re-evaluating the global $k$-value.

2. 2.

   Secondary Objective: Total Crossing Number. If a move does not change the local maximum $k$-value, the decision is based on the change in the total number of crossings, as in the previous phase.

A move is accepted if it improves the solution according to this objective. Worsening moves are still accepted based on the same probabilistic formula, using the fitness change as $\mathrm{\Delta }E$. This dual-objective approach allows the search to fine-tune the placement of nodes that are bottlenecks for the $k$-value, while still encouraging a general reduction in crossings.