Using Reinforcement Learning to Optimize the Global and Local Crossing Number

• URL: http://arxiv.org/abs/2509.06108v1
• Date: Sun, 07 Sep 2025 15:43:59 GMT
• Title: Using Reinforcement Learning to Optimize the Global and Local Crossing Number
• Authors: Timo Brand, Henry Förster, Stephen Kobourov, Robin Schukrafft, Markus Wallinger, Johannes Zink,
• Abstract summary: 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.
• Score: 2.1753067041165304
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. In our framework, an agent learns how to move a vertex based on a given observation vector in order to optimize its position. 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. We see a potential for further development of the approach in the future.

Related papers

• Policies over Poses: Reinforcement Learning based Distributed Pose-Graph Optimization for Multi-Robot SLAM [1.3750624267664158]
  We consider the sequential distributed pose-graph optimization (PGO) in multi-robot localization.<n>We cast PGO as a partially observable game defined on a Markov Neural Network (GNN), where each action refines a single edge's pose estimate.<n>We show that our learned actors reduce the global trajectory by an average of 37.5%, while enhancing efficiency by at least 6X.
  arXiv  Detail & Related papers  (2025-10-26T16:21:24Z)
• Fast Geometric Embedding for Node Influence Maximization [49.84018914962972]
  We introduce an efficient force layout algorithm that embeds a graph into a low-dimensional space, where the radial distance from the origin serves as a proxy for centrality measures.<n>As an application, it turns out that the proposed embedding allows to find high-influence nodes in a network, and provides a fast and scalable alternative to the standard greedy algorithm.
  arXiv  Detail & Related papers  (2025-06-09T05:21:56Z)
• Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference [18.101059380671582]
  We study multi-armed bandits under network interference.<n>This induces an exponentially large action space.<n>We propose a novel algorithm that uses the local graph structure to minimize regret.
  arXiv  Detail & Related papers  (2025-03-10T17:25:24Z)
• Graph Convolutional Branch and Bound [1.8966938152549224]
  We propose using neural networks to learn informatives-most notably, an optimality score that estimates a solution's proximity to the optimum.<n>This score is used to evaluate nodes within a branch-and-bound framework, enabling a more efficient of the solution space.
  arXiv  Detail & Related papers  (2024-06-05T09:42:43Z)
• Multiway Point Cloud Mosaicking with Diffusion and Global Optimization [74.3802812773891]
  We introduce a novel framework for multiway point cloud mosaicking (named Wednesday) At the core of our approach is ODIN, a learned pairwise registration algorithm that identifies overlaps and refines attention scores. Tested on four diverse, large-scale datasets, our method state-of-the-art pairwise and rotation registration results by a large margin on all benchmarks.
  arXiv  Detail & Related papers  (2024-03-30T17:29:13Z)
• Graph Transformer GANs with Graph Masked Modeling for Architectural Layout Generation [153.92387500677023]
  We present a novel graph Transformer generative adversarial network (GTGAN) to learn effective graph node relations. The proposed graph Transformer encoder combines graph convolutions and self-attentions in a Transformer to model both local and global interactions. We also propose a novel self-guided pre-training method for graph representation learning.
  arXiv  Detail & Related papers  (2024-01-15T14:36:38Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  We study the problem of multi-robot active mapping, which aims for complete scene map construction in minimum time steps. The key to this problem lies in the goal position estimation to enable more efficient robot movements. We propose a novel algorithm, namely NeuralCoMapping, which takes advantage of both approaches.
  arXiv  Detail & Related papers  (2022-03-30T14:03:17Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.