Learning Minimally Rigid Graphs with High Realization Counts

1 Introduction

Consider a fixed team of n robots moving collaboratively in the plane. Each robot is equipped with only a few sensors (typically far fewer than n - 1) that measure and enforce fixed distances to some of the others, thereby imposing a set of pairwise distance constraints on the formation. From these distances alone, can we guarantee that the formation cannot continuously deform into a different shape while keeping all measured distances unchanged, so that the robots can reliably synchronize their motion? The sensing pattern is captured by a measurement graph whose vertices represent robots and whose edges indicate pairs for which a distance is available. Mathematically, this is formalized by notions from Rigidity Theory [Sitharam et al., 2018]: a planar realization of the measurement graph is called rigid if it admits no nontrivial continuous deformation that preserves all edge lengths; otherwise, it is called flexible; see Figure 1.

However, even if a realization is rigid, the same edgelength data may still admit (finitely) many distinct realizations up to rigid rotations and translations; see Figure 2.

Extended version: DOI:10.48550/arXiv.2605.12427

Repository: https://github.com/Esestree/RL-min-rigid-graphs

2

3

1

4

Determining the number of these realizations has attracted a lot of attention: from (asymptotic) bounds (e.g. [Borcea and Streinu, 2004; Bartzos et al., 2023; Clarke et al., 2026]), via exact numbers for special cases [Jackson and Owen, 2019] and algorithms for computation [Capco et al., 2018; Gallet et al., 2020; Grasegger et al., 2024; Dewar et al., 2025], to computational search for graphs maximizing it [Grasegger et al., 2020; Capco, 2024; Grasegger, 2025]. For the robots, this means that distance measurements alone need not single out a unique placement of the team; instead, they may determine a finite set of feasible formations that all satisfy the same sensing constraints. This multiplicity is not only a source of ambiguity, but can also be seen as a form of built-in variability: the robots may be positioned in different geometric arrangements while preserving the same set of measured distances. For instance, in bar-and-joint linkages (robots as joints, distances as bars), this non-uniqueness has been used to design multistable compliant structures [Zhang et al., 2021]. Moreover, graph rigidity properties have been applied in various fields beyond multi-robot control [Zelazo et al., 2015; Krick et al., 2009], including sensor network localization [Zhu et al., 2010], molecular biology [G´asp´ar and Csermely, 2012; Billinge et al., 2016], and architecture [Vilnay et al., 2023].

In this work, we study the problem of finding minimally rigid graphs with high values of selected rigidity invariants, such as the finite number of planar realizations up to rotations and translations. On the one hand, this is an extremal optimization problem over a rapidly growing combinatorial domain (e.g., ∼ 1012 minimally rigid graphs for n = 15; [Larsson, 2020]), making exhaustive enumeration and evaluation for large n infeasible. On the other hand, improving empirical bounds and understanding the structure of extreme graphs can inform the design of measurement graphs in applications and shed light on the combinatorial and algebraic mechanisms that govern rigidity phenomena. Prior work has relied either on exhaustive search for small n [Capco, 2024], or extensive computations combined with expert knowledge [Grasegger et al., 2020; Grasegger, 2025].

In contrast to previous work, we employ reinforcement learning (RL) to search for minimally rigid graphs with exceptionally many realizations. Concretely, constructing a minimally rigid graph Gn on n vertices can be formulated as a sequential decision-making problem using so called 0- and 1extensions (introduced by [Henneberg, 1903]) that add a new vertex each time. At step k, the current intermediate rigid graph Gk defines a state sk ∈ S; each admissible extension of Gk that yields a rigid graph Gk+1 corresponds to an action ak ∈ A; and the value of a chosen rigidity invariant (e.g., the number of realizations of the terminal graph Gn) serves as the reward. The objective is to learn a policy π that, given a state sk, selects actions ak that transformGk into Gk+1, and repeats this process until reaching a final graph Gn with high reward. We address this problem via the Deep Cross-Entropy Method (Deep CEM), which iteratively updates a stochastic policy over graph extensions by biasing sampling toward elite construction trajectories. To represent intermediate graphs, we employ a Graph Isomorphism Network (GIN) encoder, and we design an extension-level, permutation-equivariant policy module so that action probabilities transform consistently under vertex relabeling. Our main contributions can be summarized as follows:

• We formulate the construction of minimally rigid graphs with large realization counts as a sequential decisionmaking problem and, to our best knowledge, we are the first to propose a RL framework with permutationequivariant action representations for its solution.
• We demonstrate through extensive empirical study that our approach matches the known optima in the planar case and improves the best known lower bounds on the sphere for larger n, including new record graphs for spherical realization counts.
• Of particular relevance, our method is orders of magnitude faster than previous attempts and yields extremal graph instances that can potentially provide evidence toward a better understanding of structural phenomena in rigidity theory, which we further discuss (see Results in Section 4 and the extended version).
• We study the transfer-learning properties of our method and ablate our encoder (in the extended version).

2 Preliminaries and ProblemDefinition

Basic Notation. We consider only simple undirected graphs. Let G = (V, E) be a graph with n = |V | vertices and |E| edges. We denote the edge formed by vertices u and v by uv ∈ E. Since the edges are undirected, uv ∈ E is the same as vu ∈ E. We denote by Kn the clique on n vertices.

2.1 Minimally Rigid Graphs

We briefly recall the definition of minimally rigid graphs for completeness and to fix notation. To this end, we first introduce flexible and rigid realizations, and then define generic rigidity and minimal rigidity. For a comprehensive treatment, we refer to [Sitharam et al., 2018, Part IV].

Definition 1 (Flexible and Rigid Realizations). A planar realization of a graph G = (V,E) is a map p: V → R2 . It is called flexible if it has a nontrivial flex, that is, a continuous path of planar realizations pt, t ∈ [0, 1], with p0 = p such that for all t ∈ (0, 1], ||p(u)-p(v)|| = ||pt(u)-pt(v)|| holds for every edge uv ∈ E, but ||p(u)-p(v)|| ̸= ||pt(u)-pt(v)|| for some vertices u, v ∈ V . Otherwise, the realization is called rigid.

In particular, for flexible realizations, the requirement that the flex is nontrivial rules out translations and rotations of the entire framework and ensures that the deformation changes the shape of the realization.

Definition 2 (Generic and Minimal Rigidity). A planar realization is generic if the coordinates of the vertices are algebraically independent over the rational numbers. A graph G is rigid if any (equivalently, every) generic planar realization is rigid. Otherwise, the graph is called flexible. A graph is minimally rigid if it is rigid and the deletion of any edge yields a graph that is flexible.

2.2 Rigidity Invariants

We study three rigidity invariants for minimally rigid graphs. Given a minimally rigid graph G, we consider: (i) the number of (complex) planar realizations of G; (ii) the number of (complex) spherical realizations of G; and (iii) the number of NAC-colorings of G.

Given a generic planar realization p of a minimally rigid graph G = (V,E), we aim to count the realizations of G that have the same edge lengths as p, modulo rotations and translations. Note that this number is finite, but it might vary between different choices of p (see for instance [Jackson and Owen, 2019]) as this corresponds to the number of solutions of the following polynomial system over the real numbers:

where (xu, yu) denotes the coordinates of vertex u ∈ V and some edge ¯u¯ v ∈ E is pinned down to factor out the rotations and translations. However, the number of solutions over the complex numbers is the same for all generic realizations p of the graph G [Jackson and Owen, 2019, Theorem 3.6] and upper bounds the number of (real) realizations.

Definition 3 (The number of planar realizations). Let G be a minimally rigid graph. The number of (complex) planar realizations of G, denoted by Plane#(G), is the number of complex solutions of (1) for any generic realization p of G.

Similarly as we have defined planar realizations, spherical realizations and their rigidity can be defined by replacing R2 by the 2-dimensional sphere. The generic rigidity behavior in the plane and the sphere is the same (see for instance [Dewar and Grasegger, 2024, Theorem 2.5]), namely, a graph is minimally rigid in the plane if and only if it is minimally rigid on the sphere. Hence, one may consider rigid graphs without specifying whether rigidity is studied in the plane or on the sphere. A polynomial system of equations similar to (1) corresponding to spherical realizations can be formulated using inner products on the left hand side. The number of complex solutions of the system is then called the number of spherical realizations of a minimally rigid graph G and is denoted by Sphere#(G). See [Dewar and Grasegger, 2024, Section 4] for a rigorous definition.

Finally, we consider a third rigidity-related invariant (NAC#, also defined for flexible graphs), defined via certain two-color edge assignments as follows.

Definition 4 (NAC-colorings). A surjective edge coloring of a graph G by red and blue is called a NAC-coloring if for every cycle of G, either all edges have the same color, or there are at least two blue and two red edges. Let NAC#(G) denote the number of NAC-colorings of G divided by two (which corresponds to swapping the colors).

NAC-colorings are interesting from the rigidity point of view, since they yield flexible realizations. More precisely, a connected graph has a planar realization with a flex if and only if it has a NAC-coloring [Grasegger et al., 2019]. Interestingly, rigid graphs can have (non-generic) realizations with a flex. Different NAC-colorings give different flexes (see [Clinch et al., 2026, Section 2.2]), hence it is natural to ask for minimally rigid graphs with many NAC-colorings.

2.3 Optimization Problem

Fix n ≥ 2 and let Mn be the set of minimally rigid graphs on n vertices. For a chosen rigidity invariant R : Mn → R≥0 (e.g., R = Plane#, R = Sphere#, or R = NAC#), we consider the following optimization problem:

Since Mn grows super-exponentially (see the extended version) and evaluating R(G) can be expensive, directly solving (2) is infeasible beyond small n. Thus, we pursue an approximate solution via RL, by learning a policy that constructs high-reward graphs through sequential extensions.

3 Methodology

3.1 Deep CEM for Minimally Rigid Graphs

In our task of generating minimally rigid graphs with high realization counts, we propose a framework based on the Deep CEM. Classical CEM [Rubinstein and Kroese, 2004] iteratively samples candidates from a simple parametric distribution (e.g., a Gaussian) and updates the distribution to concentrate probability mass around the highest-performing (elite)

solutions. Deep CEM extends this idea by replacing the simple parametric distribution with a stochastic policy network πθ, which can represent complex and structured distributions (e.g., over graph extensions). A stochastic policy network with parameters θ can be seen as a mapping

where S is the state space, A is the action space, and ∆(A) denotes the set of probability distributions over A. For each state s ∈ S, πθ(· | s) is a probability distribution over actions in that state, satisfying ∑a∈A πθ(a | s) = 1. Thus, the value πθ(a | s) gives the probability of selecting action a in state s.

In our setting, a state s corresponds to an intermediate graph Gk in the construction process. Rolling out the policy πθt (at step t) from the base graph K2 (the clique on two vertices) many times produces construction sequences

where each transition Gk → Gk+1 is obtained by sampling an extension from πθt (· | Gk). Extensions are particularly natural choices to define the action space A, because a graph G is minimally rigid if and only if it can be obtained from K2 by a finite sequence of 0- and 1-extensions (see e.g. [Sitharam et al., 2018, Theorems 19.2 and 19.11]), whose definition we recall now. Let G = (V,E) be a graph, and let z /∈ V be a new vertex. If u, v ∈ V are distinct vertices, then the graph

is called a 0-extension of G. If u, v,w ∈ V are distinct vertices and vw ∈ E, then the graph

is called a 1-extension of G; for illustration, see Figure 3. Thus, for a transition from Gk to Gk+1, we define the action space A as the set of all 0-extensions and 1-extensions applicable to Gk.

Having fixed the reward function R: Mn → R≥0 for a given rigidity invariant (e.g., R = Plane#), we now describe how Deep CEM is instantiated in our setting; see Algorithm 1. For a given number of vertices n, and number of generations T, we maintain a population of m constructions and iteratively refine a stochastic policy πθ over 0- and 1-extensions. At generation t, we start from the current survivor set St-1 and build a population Pt. Each new candidate is obtained by rolling out the policy from the base graph K2: at step k we sample an extension ak ∼ πθt (· | Gk), apply it to obtain Gk+1, and repeat until we reach Gn. Because the action space consists only of 0- and 1-extensions, every sampled Gn is minimally rigid by construction.

Algorithm 1 Deep CEM for Minimally Rigid Graphs

Require: number of vertices n; population size m; number

of generations T; survivor fraction ρsurv; elite fraction ρelite; reward function R: Mn → R≥0 1: S0 ← ∅ ; θ1 ← initialize policy parameters 2: for t = 1 to T do ▷ for details, see the ext. version 3: Pt ←St-1 ▷ current population of constructions 4: while |Pt| <mdo 5: G2 ← K2 6: for k = 2 to n - 1 do 7: sample extension ak ∼ πθt (· | Gk) 8: Gk+1 ← Apply(Gk, ak) 9: end for 10: add Gn to Pt 11: end while 12: Ωt ← top ⌊mρelite⌋ graphs in Pt by R(G) 13: build dataset D = ⋃G∈Ω{(Gk, ak)}n-1 k=2 14: θt+1 ← Update(θt; D, L) 15: St ← top ⌊mρsurv⌋ graphs in Pt by R(G) 16: end for 17: return ˆG⋆ ← argmaxG∈St R(G)

We then evaluate the reward R(G) for all G ∈ Pt and select an elite set Ωt comprising the top ⌊mρelite⌋ graphs. From each G ∈ Ωt we extract the sequence of state-action pairs {(Gk, ak)}n-1 k=2 and aggregate them into a dataset Dt. Next, we update the policy parameters from θt to θt+1 by minimizing for few epochs L(θt) (Eq. 4) on Dt using Adam. The survivor set St for the next generation is then taken as the top ⌊mρsurv⌋ graphs in Pt. After T generations, the algorithm outputs

an n-vertex minimally rigid graph with a large value of R(G). For computing R ∈ {Plane#, Sphere#}, we use the package LNUMBER [Capco, 2024] which is based on [Capco et al., 2018] and [Gallet et al., 2020] respectively. For NAC#, we use the algorithm [Laˇstoviˇcka and Legersk´y, 2024] implemented in the package PYRIGI [Adrian-Himmelmann et al., 2026].

Remark. During graph generation, we must score thousands of candidates to form the elite set Ωt in each generation t (see Algorithm 1, line 12). Since exact evaluation of Plane# and Sphere# is costly, we use the efficiently computable upper bound m-B´ezout(G) [Bartzos et al., 2020] as a surrogate during sampling. In particular, m-B´ezout(G) upper-bounds the realization-count objectives, i.e.,

(see [Dewar and Grasegger, 2024] for the first inequality). In practice, we first score all graphs in a generation with m-B´ezout(G) and then compute the true reward (Plane# or Sphere#) only for the top 25% candidates. This two-stage screening yields a significant speedup in our experiments while maintaining good agreement with the exact reward on the selected candidates. For details, we refer to the extended version.

3.2 Stochastic Policy Network Architecture

In this section, we describe the architecture of our stochastic policy network, which is illustrated in Figure 4.

Graph Encoder. The input to the policy at step k is an intermediate (minimally rigid) graph Gk = (Vk, Ek). Since the choice of extensions must depend only on the underlying unlabeled combinatorial structure, we require the policy to be permutation-equivariant: relabeling the vertices of an intermediate graph Gk with permutation σ permutes the policy's output in the corresponding way:

Moreover, the rigidity invariants we study are themselves invariant under vertex relabeling.

Thus, a natural graph neural network encoder for this setting is the Graph Isomorphism Network (GIN) [Xu et al., 2019]. GIN not only discriminates between different graph structures but also maps similar structures to similar embeddings, capturing dependencies between graph components. At a high level (we refer to the original work for details), a GIN layer aggregates features from a vertex's neighbors, combines them with the vertex's own features, and applies a learned transformation. Formally, the hidden representation h(l) v of vertex v at layer l ∈ {1, 2, . . . ,LG} is given by

where N(v) denotes the neighbors of v, ϵ(l) is a learnable scalar and MLP(l) denotes a multilayer perceptron. The initial vertex features h(0) v encode basic local structural information around each vertex and serve as the input to the first GIN layer. Note that GIN may fail to capture certain substructures and to distinguish between specific classes of graphs (e.g., regular graphs, certain trees or other graphs that share the same degree multiset) when all vertices share the same feature values, because they were shown to be at most as powerful as the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test [Huang and Villar, 2021].

To better expose rigidity-relevant structure to the encoder, we therefore augment vertices with explicit local structural features. In particular, prior work on rigidity invariants [Grasegger, 2025] observed recurring patterns in graphs with high Plane# or Sphere#, including characteristic degree multisets, constraints on triangle counts, or degree- and Hamiltonicity-driven adjacency rules. These observations indicate that degree-related structural properties are highly relevant for characterizing graphs with favorable rigidity invariants. Thus, for each vertex v ∈ Vk, we build a Local Degree Profile (LDP) [Errica et al., 2019] defined as

where deg(v) is the degree of vertex v. In summary, we define the initial vertex features as

where λk ∈ Rd is a learnable embedding of the current construction step k (making the policy step-aware), and κv is the clustering coefficient of v, defined for unweighted graphs as the fraction of potential triangles through v that are present:

with τ(v) denoting the number of triangles incident to v. Finally, we define the initial vertex features as H(0) = (h(0) v )v∈Vk and denote by hv = h(LG) v the encoded representation of vertex v, i.e., the output of the final GIN layer.

Permutation-Equivariant Extensions Representation Module. We first pass the initial vertex features through our encoder (GIN layers) and obtain vertex representations H = (hv)v∈Vk . Our goal is then, based on H, to construct an architecture that assigns probabilities to each extension. Note that the extensions are defined in terms of specific vertex tuples (e.g., a 1-extension on (u, v,w)); therefore, under a relabeling of vertices, the set of valid extensions is permuted accordingly. Consequently, for isomorphic graphs G and G′ , the desired behavior is that the policy on G′ is a permutation of the policy on G (see (3)).

Thus, we must construct extension-level representations E from vertex embeddings H so that action scores transform equivariantly under graph isomorphisms. Observe that, in an intermediate graph Gk, a candidate 1-extension acting on vertices u, v,w with removal of edge vw can be encoded by (u, {v, w}). For all distinct u, v, w ∈ Vk, we consider

where ϕ(·) and ψ(·) are permutation-invariant functions (see [Zaheer et al., 2017]), and γ(u,v,w) is a feature vector encoding additional properties of the extension. If vw /∈ Ek, we say that (u, {v,w}) is invalid, otherwise e(u,{v,w}) represents a 1-extension. Note that 0-extensions can be modeled as a special case of the above construction by introducing a dummy vertex ∅ with embedding h∅ = ⃗0. A 0-extension acting on vertices u and v is then represented as

so that both 0- and 1-extensions share the same extension representation space E. Furthermore, γ(u,v,w) ∈ {0, 1}5 collects five extension-specific features

where each component is a binary indicator: 1invalid denotes whether (u, {v,w}) is invalid, 1E0 indicates a 0-extension, and 1E1a , 1E1b , 1E1c indicate the 1-extension subclasses identified in [Grasegger, 2025], which differ only in the number of edges connecting the three vertices. Exactly one of the features 1invalid, 1E0 , 1E1a , 1E1b , 1E1c is equal to 1.

Remark. We encode extension validity via the binary feature 1invalid instead of removing invalid moves. This keeps a uniform extension representation and lets a shared extensionscoring MLP process all candidates, while learning to assign (near-) zero probability to those with 1invalid = 1. This soft treatment stabilizes training (invalid moves still receive gradients) and preserves permutation structure. In the rare case of an invalid extension is sampled, we simply discard it and resample, so the construction remains minimally rigid.

Extension-scoring Head. Finally, we feed each ei ∈ E through an LE-layer MLP, applied element-wise with shared parameters, so that the final layer produces a scalar logit zi for each extension while preserving equivariance. Collecting these into a vector z ∈ R|E| and applying a softmax,

yields a probability distribution p over candidate extensions, where p(u,{v,w}) is the probability of selecting the extension indexed by (u, {v, w}) with u ∈ Vk ∪ {∅} and v, w ∈ Vk.

3.3 Loss Function

A central challenge in reinforcement learning is achieving a suitable trade-off between exploration and exploitation. In our setting, this is particularly critical: we search for extremely rare graph configurations, and insufficient exploration can cause the policy to converge prematurely to suboptimal structures. To explicitly address this requirement, we adopted Entropy regularization. This regularization technique augments the training objective (negative loglikelihood of elite actions) with an entropy term that penalizes overly confident action distributions:

where H(πθ(· | s)) = - ∑a∈A πθ(a | s) logπθ(a | s) is the entropy of the action distribution at state s, and η ∈ R≥0 controls the strength of entropy regularization. As training progresses, the model acquires more information about which actions are beneficial. If entropy is kept too high, the policy may remain overly stochastic and fail to reliably construct high-quality graphs. To balance this, we gradually decrease the entropy coefficient over generations:

where η0, α, and β are hyperparameters, and t ≤ T indexes the generation. This schedule encourages broad exploration in the early stages and progressively shifts the policy toward exploitation of the most promising graph constructions. Although other methods can be similarly efficient in practice, entropy regularization has some unique properties. First, because it modifies the objective, it encourages the network to build good constructions, while being as uncertain in action choices as possible, which helps in creating diverse generations of good constructions. Second, the network learns to concentrate its 'confidence budget' on terminal actions, optimizing the final steps to maximize rewards even when preceding actions were chosen randomly.

4 Experiments

We evaluate our method on Plane#, Sphere#, and NAC#. We focus on the range 10 ≤ n ≤ 18, matching the intervals most extensively studied in prior computational work and for which reference optima or best-known bounds are available. For small n, exhaustive enumeration provides groundtruth optima, whereas for larger n we compare against the strongest previously reported values. For further details on reproducibility (including hardware specifications) and hyperparameter choices, we refer to the extended version and the accompanying repository [Slyvka et al., 2026].

Baselines and Metrics. We compare our method in terms of (i) the best realization counts reported in the literature and (ii) runtime. For the number of realizations, we compare against [Clinch et al., 2026; Grasegger, 2025], which includes also the results obtained previously by [Grasegger et al., 2020; Capco, 2024]. The timing for the results from [Grasegger, 2025] were obtained as follows: for the results known to be optimal, we measured the exhaustive search using [Capco, 2024] except for the largest number of vertices, where the timing was extrapolated using the numbers of non-isomorphic minimally rigid graphs (from [Larsson, 2020]). Since [Grasegger, 2025] claims that several millions of graphs with n ≥ 15 were checked to get the indicated bounds on Plane#, without providing any timing, we estimate the time of computing Plane# for one million of graphs with 15 vertices (using the average time to compute Plane#(G) for 15-vertex graphs G we have encountered), similarly with half milion 14-vertex graphs for Sphere#. Note this is a (very) conservative estimate; in reality it may be (much) higher. For our model, to initialize parameters for the computation of Plane# on n = 18 vertices, we used the weights of the model trained for n - 1 vertices, and similarly for Sphere# for n ∈ {16, 18}; hence, we include this pretraining in the timing.

Results. The results we obtained are summarized in Table 1. Besides the timings, we indicate also for how many graphs the rigidity invariants were evaluated. Remarkably, the number of graphs needed for training is by several orders of magnitude lower than the number of minimally rigid graphs. For instance, for n = 15, we evaluate Plane# and Sphere# only for less than 105 out of the almost 1012 graphs. Empirically, the number of minimally rigid graphs on n + 1 vertices is expected to be at least 30× larger than on n. However, we observe that the number of graph evaluations required by our method to find constructions with high rigidity invariants increases only mildly as n grows. Thus, the longer computation times are caused by the (costly) reward evaluation for larger graphs, especially for Sphere#, rather than by the number of evaluated graphs (see N in Table 1).

For Plane#, we found exactly the same (i.e., isomorphic) graphs and therefore also the same values as [Grasegger, 2025]. However, for larger n, our method finds them orders of magnitude faster than exhaustive search. Note that the implementation [Capco, 2024] is already optimized, for instance, it skips graphs with a vertex of degree two as it is known these cannot attain the maximum.

In contrast to the planar case, for 15 ≤ n ≤ 18 we find graphs with larger Sphere# than [Grasegger, 2025], establishing new best-known lower bounds for the maximum value of this invariant. The 14-vertex graph we found is isomorphic to the one reported in [Grasegger, 2025]. It is known that the maximum can be attained by several graphs. We found two different graphs on 15 with the indicated number of spherical realizations, whereas for n ≥ 16 we found a single new graph attaining our best value. Previously, multiple graphs attaining to the maximum have been reported only for n ≤ 13, i.e., coming from exhaustive search. The previously reported best graphs are Hamiltonian and have chromatic number three, minimum degree three and maximum degree four. While for those the search might have been biased towards having these properties, the graphs we have found possess them as well without imposing them. Previously, the graphs contained at least two 3-cycles, while one of our 15vertex graphs and those with 16, 17 and 18 vertices have even stronger property: every vertex is in a 3-cycle.

Regarding NAC#, [Clinch et al., 2026] does not explicitly provide graphs with many NAC-colorings on 13 to 17 vertices. Hence, we constructed them using the same method as the one with 18 they provide. Our method gives better graphs for all 13 ≤ n ≤ 18. As expected, none of the graphs contains a 3-cycle since its edges have to be of the same color. Interestingly, our graphs on 13, 15 and 16 vertices can be constructed from the complete bipartite graph on 3 + 3 vertices using only 0-extensions, and we have observed such graphs also on 14 and 17 vertices that have NAC# close to the found maximum. The fact that these graphs can be constructed in similar manner could be potentially used to obtain an infinite family of graphs with many NAC-colorings. The graphs with 14, 17 and 18 have non-trivial automorphism groups and minimum degree three (i.e., the last step is a 1-extension). Instantiating [Clinch et al., 2026, Lemma 5.6] with the 18vertex graph, we get a new asymptotic lower bound 2.144n on the maximum number of NAC-colorings.

We provide the graphs for the improved bounds in the extended version and our repository [Slyvka et al., 2026].

5 RelatedWorks

A fundamental work by [Wagner, 2021] introduced a general reinforcement-learning framework for combinatorial constructions, modeling them as sequential decision processes and showing that neural policies can effectively guide search toward high-quality mathematical objects. Building on this line of research, [Angileri et al., 2025] analyzed Wagner's framework on Brouwer's conjecture. Like us, they experimented with a Deep CEM-style scheme, but they target conjecture-driven graph search rather than rigidity optimization and do not require permutation-equivariant, extension-level action representation like ours. Furthermore, works such as [Charton et al., 2024] and [Mehrabian et al., 2024] propose effective methods for searching large extremal graphs (e.g., for Erd˝os-type conjectures), using sophisticated architectures, including transformers, AlphaZero integrated with Pairformer modules, and metaheuristics like incremental Tabu search. However, these approaches are not well suited to our setting: they typically require generating and evaluating very large numbers of candidate graphs, which would be prohibitively here because computing rigidity invariants is the main computational bottleneck. More recently, [Georgiev et al., 2025] demonstrated that combining evolutionary methods with large language models can enable mathematical discovery across a wide range of domains, albeit at the cost of relying on potentially expensive language-model infrastructure. In contrast, our approach is specialized to rigidity-theory invariants and provides an efficient and accurate search procedure without dependence on external models or sources.

To our best knowledge, no comparable machine learningbased approach has yet been applied to optimizing rigidity invariants. In a related vein, while we focus on complex realizations, [Bartzos et al., 2021] studied the number of real realizations using a heuristic-based search. For complex realization counts, prior work has relied either on exhaustive search for small n [Capco, 2024] or on large-scale computations guided by expert insight [Grasegger et al., 2020; Grasegger, 2025], similarly for NAC# [Clinch et al., 2026].

6 Conclusion

We introduced a learning approach to the extremal problem of finding minimally rigid graphs with large rigidity invariants. Empirically, we (i) recover the known optimal values for planar realization counts and (ii) establish improved best-known lower bounds for spherical realization counts (for 15 ≤ n ≤ 18) and for the number of NAC-colorings (for 13 ≤ n ≤ 18), while evaluating only a tiny fraction of all candidate graphs. Future work will focus on the structural features of the discovered extremal graphs and leverage them to derive new theoretical insights in rigidity theory and the extension of our framework to other invariants and larger n.

Ethical Statement

The research is primarily foundational and is unlikely to have any significant ethical impact.

Acknowledgments

This work was supported by the Student Summer Research Program 2025 of FIT CTU in Prague. J. L. was supported by the Czech Science Foundation (GAˇCR), project No. 2204381L.