## On the Genus of One Degree of Freedom Planar Linkages via Tropical Geometry

J. Schicho, A. K. Tewari, A. Warren

January 30, 2025

## Abstract

This paper focuses on studying the configuration spaces of graphs realised in C 2 , such that the configuration space is, after normalisation, one dimensional. If this is the case, then the configuration space is, generically, a smooth complex curve, and can be seen as a Riemann surface. The property of interest in this paper is the genus of this curve. Using tropical geometry, we give an algorithm to compute this genus. We provide an implementation in Python and give various examples.

## Introduction

Let G = ( V, E ) be an undirected simple graph without self-loops. Intuitively, a planar realisation of G consists of a point in the real plane for every vertex and a straight line segment for every edge (edges may intersect). Let us prescribe a real number for every edge. Then a realisation such that the squared length of every edge is equal to the prescribed number is called a configuration of the graph (together with the assignment of numbers to edges). The set of configurations is an algebraic variety given by | E | equations in 2 | V | variables. If we have any realisation, then any translation or rotation of a configuration is again a configuration for the same edge numbers. We can normalise: pick an edge and fix its endpoints beforehand. The normed realisations form an algebraic variety with | E | -1 equations in 2 | V | -4 variables.

In this paper, we look at the complexification of the variety of normed realisations (given by the same equations, but variables range over the complex numbers). If the assigned edge numbers are generic, then the set of normalised configurations is a nonsingular algebraic variety of dimension 2 | V | - | E | -3, if it is not empty. The case of minimally rigid graphs is classical (see [4, 10]): in this case, 2 | V | - | E | -3 = 0, and for generic edge numbers we have a finite set of configurations. This finite number is independent of the choice of edge numbers as long as they are generic, and

it is therefore an invariant of the graph called the Laman number . A combinatorial algorithm for computing the Laman number of a given minimally rigid graph is given in [5].

A one degree of freedom linkage/graph (1-dof, also called a calligraph), is obtained by removing one edge from a minimally rigid graph. In this case, the configuration set is a nonsingular algebraic variety of dimension 1. It may be reducible; the number of irreducible components is equal to the product of all maximal subgraphs that are minimally rigid, by [13]. Our result here is an algorithm that computes this genus. Notice that the genus does not depend on the choice of edge numbers as long as they are chosen generically, because each generic fiber is defined by essentially the same equations over the field generated by the edge numbers. As an application, we give an answer to 'Open Problem 3' in [6], which asks for the genus of the plane curve traced by a single vertex while an edge is kept fixed. A classically known case is the 4-cycle, also known as four-bar linkage. Here, the configuration set is an irreducible curve of genus one (see [8]).

Tropicalization has been used in [5, 1, 3] to prove statements about Laman numbers of minimally rigid graphs. By some linear change of variables, one can reduce the system of algebraic equations that defines the configuration set of a graph to a system of linear equations that depend on the graph together with equations s t e e = λ e , with e ranging over all edges and s , t e e are indeterminates. The tropicalization process transforms these quadratic equations into linear equations of the form x e + y e = w e , where x e and y e are tropical variables and w e is a tropical (generic) parameter. The tropicalized system of equations consists of linear equations and inequalities, and its solution set is a tropical variety, the tropicalized configuration set. If G is minimally rigid, then the tropical variety is a finite set of points, and its cardinality is the Laman number. If G is a 1-dof graph, then we have a disjoint union of tropical curves. We show that the genus of an irreducible component of the fiber is equal to the genus of the any of these tropical curves. Note that in general, the genus of an algebraic curve may be different from the genus of its tropicalization; however, if the tropicalization is tropically smooth, or equivalently if the algebraic curve is a Mumford curve, then the algebraic genus and the tropical genus coincide [11].

Our algorithm computes the tropical curve explicitly; once this is achieved, computing the genus amounts to counting edges and vertices. We compute a point on the tropicalization of the generic configuration space by a probabilistic algorithm. Then we compute the directions of the edges incident to this point and follow them to the next vertex. We repeat this until no new edges and vertices are found, iteratively traversing the whole tropical curve.

For each new vertex we find, we test a condition that implies that the tropical curve is smooth at that vertex, namely the transversality of the intersection of the Bergman fan of the graph and a mirror copy of the Bergman fan. If all tests are affirmative, then we compute the genus. In the unlikely case that we receive a negative test result, we give an error message. In this case, we can start over again by computing probabilistically a new starting point.

We have implemented the algorithm in Python; the code can be found at the GitHub repository AudieWarren/1dof-Graph-Genus-Code . In order to use the code, download the folder 'Modu-

larversion'. In the file 'graphgeneration' you can input the edges of your graph, with many examples already being in the file. Then simply run the 'main' file; the programme will output the genus of the curve, together with a visualisation of the tropical curve. Note that you may have to install Networkx via pip for the code to run.

## 1 The Precise Statement of the Problem, and a Theorem on Tropical Curves

## 1.1 The Precise Statement of the Problem

For any graph G = ( V, E ) on n ≥ 2 vertices with at least one edge, we label the vertices so that { 1 2 , } ∈ E . In order to analyse the realisations of this graph, we fix the vertex 1 at the origin, and the vertex 2 to the point (1 , 0). This removes the trivial motions of the graph via elements of SE (2), and allows us to define the two-dimensional (normalised) edge map of G in the following way.

↦

$$f _ { G } \colon \mathbb { C } ^ { 2 | V | - 4 } & \to \mathbb { C } ^ { | E | - 1 } \\ ( x _ { i }, y _ { i } ) _ { i \in V \subset \{ 1, 2 \} } & \mapsto \left ( ( x _ { i } - x _ { j } ) ^ { 2 } + ( y _ { i } - y _ { j } ) ^ { 2 } \right ) _ { i, j \in E \overline { \{ 1, 2 \} } }.$$

This map takes input positions in C 2 for the vertices, and calculates the squared distances along edges. In this paper, we define a generic element of C d (for any d ) to be any point whose coordinate entries are algebraically independent over Q . Any two generic elements are algebraically indistinguishable; more precisely, there are is a field isomorphism that preserves any variety/map defined over Q taking the first generic point to the second one. In this way, we study the generic fiber of the edge map f G -this means the fiber of any generic element of C | E |-1 . This generic fiber is also referred to as the generic (normalised, complex) configuration space of G . If the map f G is generically surjective, then the generic fiber is a smooth manifold of dimension 2 | V | - | E | -3. In this paper, we assume 2 | V | - | E | = 4, in addition to the surjectivity of f G . This is equivalent to the statement that G can be obtained from a minimally rigid graph by removing a single edge. The graph can then be considered as a one degree of freedom linkage.

The number of irreducible components of the generic fiber is well-known: it is the product of the Laman numbers of all maximal subgraphs that are minimally rigid. We provide an algorithm that computes the genus of any irreducible component for a given graph that fulfills the above assumption. All irreducible components have the same genus, by [13, Proposition 38].

## 1.2 A Theorem on Tropical Curves

Tropical geometry is the piecewise linear shadow of algebraic geometry where with a modified notion of vanishing, the vanishing locus of tropical polynomials are studied with respect to the semiring

Figure 3: Examples of classical and tropical elliptic curves

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-e3153540-2ccf-4661-b5d1-a348a04b2c69.jpg)

T = ( R ∪ ∞ , min +). , We refer the reader to the standard text [16] for basics concerning tropical geometry. A tropical curve is a connected tropical variety of dimension one. By the structure theorem of tropical varieties [16, Theorem 3.3.5], a tropical curve also enjoys the structure of a balanced rational polyhedral complex. For instance, planar tropical curves are dual to regular subdivisions of the corresponding Newton polygon.

Given an irreducible algebraic curve, we can 'tropicalize' the curve, which yields a tropical curve. The algebraic curve itself may be too complicated to work with directly, but under some conditions, certain properties of the algebraic curve can still be seen in its tropical counterpart. This paper is concerned with when the property of 'genus' is retained by tropicalization, and how to calculate it explicitly. Figure 3 illustrates an example of a tropical elliptic curve alongside a classical elliptic curve; in this case the genus of the elliptic curve is reflected as the unique hexagonal cycle in the tropical elliptic curve.

For an algebraic curve C ⊆ C {{ }} t n defined over the field of Puiseux series C {{ }} t , its tropicalization Trop( C ) is defined by removing any points where any coordinate is zero, then taking the valuations of each point coordinate-wise, and then taking the Euclidean closure, that is

$$\text{Trop} ( \mathcal { C } ) \coloneqq \overline { \{ \text{Val} ( p ) \, \colon \, p \in \mathcal { C } \cap ( \mathbb { C } \{ \{ t \} \} ^ { * } ) ^ { n } \} }$$

(as a set). This set is a union of bounded line segments we call edges and unbounded line segments we call rays. Now we assign a weight, which must be positive integer, to any edge or ray, as follows: take a point on the edge, and compute the initial ideal of the ideal of the curve with respect to the order function that assigns every coordinate function to the tropical coordinate of the point we have taken. Then the weight is defined as the sum of all multiplicities of all associated primes of the initial ideal (see [16, Definition 3.4.3]). In this paper, it will never be necessary to compute weights,

since we will prove that the weights of all edges of the tropical curve that we consider are all equal to one.

We will need a notion of smoothness for a tropical curve - notions of smoothness exists for plane tropical curves (see for instance [16]), but we define a notion of smoothness for tropical curves in any dimension, which is standard and equivalent to the other notions of smoothness for tropical curves. This definition makes use of tropical (iso)-morphisms, see for instance [14, Definition 7.1.4]. A tropical morphism f between two tropical varieties T 1 and T 2 is a continuous map which is locally affine Z -linear, that is, locally is given by composition of a Z -linear map with an arbitrary real translation. A tropical morphism f : T 1 → T 2 is an isomorphism if there is a tropical morphism g : T 2 → T 1 which is inverse to f , and such that the weights of each point in T 1 and T 2 agree under the maps.

Definition 1 (Smooth Tropical Curve) . Let T ⊆ R d be a tropical curve. We say that T is smooth if for each point p ∈ T there exists a neighbourhood U p containing p , such that U p ∩ T is tropically isomorphic to the intersection of a tropical line with an open set.

The above definition can be thought of as ' a tropical curve is smooth if it is locally isomorphic to a tropical line' . To see why such a definition is important, let us see an example of an algebraic curve which is smooth, but whose tropicalization is not smooth, and whose genus is not preserved under tropicalization.

We define the tropical genus of a connected tropical curve T as the number of its (bounded) edges minus the number of its vertices plus one.

Remark 1. It is well-known that all weights of a smooth tropical curve are equal to one (see [14, Definition 8.1.1]).

Example 1. Consider the algebraic curve V ( y 3 + x 3 +1), which is a smooth curve of genus one. The corresponding tropical curve is defined by the minimum min { 3 y, 3 x, 0 } being attained twice this is precisely the same (as a set of points) as the usual tropical line in R 2 . It is, however, not smooth, since each edge has weight three. The underlying graph is a single vertex, and so has Betti number zero. So, the genus and the tropical genus are not equal.

Figure 4: The curve x 3 + y 3 +1 = 0

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-db296dc1-fd8a-4d4c-825e-67b89ae7489a.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-50d8d840-5155-4028-a1fa-a7a98ca35d43.jpg)

Figure 5: The corresponding tropical curve

Theorem 1. Let C be a smooth projective curve of genus g , such that T := Trop ( C ) is smooth. Then the tropical genus of T is equal to g .

Proof. Essentially, this is a result in [11]. The proof uses several concepts from non-archimedean analytic geometry we did not define because we will not use them anywhere else (fully faithful tropicalization, analytification, Berkovich skeleta, Mumford curves). We refer to [11, 2] for the definitions.

By [11, Theorem 5.7], smoothness of T implies that the tropicalization is fully faithful. In particular, the tropical curve T is homeomorphic to the Berkovich skeleton of the analytification of C with respect to the given tropical embedding. By [11, Theorem 5.6], the smoothness of the tropicalization also implies that C is a Mumford curve, so all its Berkovich skeleta have genus g . Therefore T has also genus g as a graph, and the claim follows from Euler's formula.

## 2 The Tropical Generic Fiber

In this section we explain the tropicalization of the generic fiber of f G , and prove that the tropical curve we obtain is smooth. (Note that this statement is stronger than smoothness of the generic fiber itself.)

## 2.1 Tropicalization

In its standard form, the generic fiber of f G is defined by distance equations of the form

$$( x _ { i } - x _ { j } ) ^ { 2 } + ( y _ { i } - y _ { j } ) ^ { 2 } = \lambda _ { e },$$

where e = { i, j } runs over all edges except { 1 2 , } , and λ e ∈ C is a generic parameter. It will be convenient for us to make a linear change of coordinates (see for instance [7]), which will simplify all such equations. We define this change of variables in the following way. For all pairs ( i, j ) such that e := { i, j } ∈ E \ {{ 1 2 , }} , and i &lt; j , we define

$$s _ { e } & \coloneqq ( x _ { j } - x _ { i } ) + i ( y _ { j } - y _ { i } ) \\ r _ { e } & \coloneqq ( x _ { j } - x _ { i } ) - i ( y _ { j } - y _ { i } )$$

This gives us 2 | E |-2 variables. After making this change, we notice that for any cycle { i 1 , i 2 , ..., i k , i k +1 = i 1 } with edges e 1 = { i 1 , i 2 } , . . . , e k = { i k , i 1 } in G , we have that

$$\sum _ { l = 1 } ^ { k } \pm s _ { e _ { l } } = \sum _ { l = 1 } ^ { k } \pm r _ { e _ { l } } = 0.$$

The sign in the l -th summand is +1 if i l &lt; i l +1 and -1 if i l &gt; i l +1 . The edge e 0 = 1 2 { , } may occur in the cycle, and in this case we add a constant of ± 1 to the sum. After making this change, the generic fiber of the edge map (i.e. the configuration space) is defined by the equations

$$s _ { e _ { 0 } } = r _ { e _ { 0 } } = 1, \ \ s _ { e } r _ { e } = \lambda _ { e }, \ \sum _ { e \in C } s _ { e } = \sum _ { e \in C } r _ { e } = 0,$$

where C ranges over every cycle in the graph. Let us denote this fiber by C . It is isomorphic (via projection to the s -coordinates) to the intersection of two manifolds in C n , where n := | E | -1. The first manifold, which we call L 1 , is the intersection of the linear subspace defined by all equations of the form ∑ e ∈ C s e = 0 with C n , and the second, denoted by L 2 , is the image of L 1 under the map ( C ∗ ) n → ( C ∗ ) n given by

↦

$$( s _ { 1 }, \dots, s _ { n } ) \mapsto ( \lambda _ { 1 } / s _ { 1 }, \dots, \lambda _ { n } / s _ { n } ).$$

In order to tropicalize the generic fiber, we first change the field from C to C {{ }} t , the field of complex Puiseux series. This does not change the number of irreducible components or the genus of C , as the two fields are actually isomorphic. We recall that the tropicalization of an algebraic variety V ⊂ ( C {{ }} t ∗ ) n is defined as the Euclidean closure of the set of all value vectors of points in V . The value of a nonzero element in C {{ }} t is its order with respect to t , which is simply a rational number.

We tropicalize the defining equations for the generic fiber C as follows. We label the (nonnormalised) edges from 1 to n = | E | -1; single subscripts now denote edges, and the normed edge is given index 0. For each parameter λ e , we just remember its value w e -the numbers w , . . . , w 1 n will be the tropical parameters of the tropical equations. Instead of the algebraic variables s , . . . , s 1 n , t 1 , . . . , t n we take tropical variables u , . . . , u 1 n , v 1 , . . . , v n ranging over R - the orientation of edges we had previously disappears at this point, since the valuation of a Puiseux series is not changed by scalar multiplication. The normed parameter w 0 corresponding to the edge { 1 2 , } and the norming variables u , v 0 0 are set to zero - the valuation of their algebraic value. Multiplication is

replaced by addition, and a sum being zero is replaced by the condition that the minimum in some sequence of numbers is attained twice. We obtain the following system.

$$u _ { 0 } = v _ { 0 } = 0 \\ \forall e \in E \, \wedge \, & \{ \{ 1, 2 \} \}, \quad u _ { e } + v _ { e } = w _ { e }$$

$$e$$

For all cycles C in G, min e ∈ C { u e } and min e ∈ C { v e } are attained at least twice .

Furthermore, once the weights w e have been fixed, we may eliminate all of the v e variables via v e = w e -u e , further reducing the ambient space to R n , given by the now fully reduced conditions

$$u _ { 0 } = 0$$

For all cycles C in G, min e ∈ C { u e } and min e ∈ C { w e -u e } are attained at least twice.

The tropicalization of the generic fiber C is contained in the zero set of the tropical equations above. We will see that it is actually equal to this zero set. To do this, we will use the following lemma.

Lemma 1. The tropicalization of the linear variety L 1 is equal to the tropical variety X defined by the tropical equations

$$u _ { 0 } & = 0 \\ F o r \ a l l \ c y c l e s \ C \ i n \ G, \ \min _ { e \in C } \{ u _ { e } \} \ i s \ a t t a i r.$$

$$G, \, \min _ { e \in C } \{ u _ { e } \} \ i s \ a t t a i n e d \ t w i c e.$$

Proof. Because L 1 is a linear space, its tropicalization is defined by all circuits, i.e. minimal supports of linear equations in the ideal of L 1 . By [16, Example 4.2.14], the circuits are exactly the cycle conditions.

In Lemma 1, we implicitly defined the tropical variety X . Now we define Y as the tropicalization of L 2 . Clearly, this is just the image of X under the map from R n to itself that sends ( x , ..., x 1 n ) to ( w 1 -x , ..., w 1 n -x n ). This map is an example of a tropical isomorphism, to be defined in the next subsection; we will need tropical isomorphisms in order to show that the tropicalisation of C is tropically smooth.

A vector w ∈ R n is called tropically generic if its coordinates are linearly independent over Q . If w is tropically generic, then it cannot be a vector of values, but the definitions of the tropical varieties X and Y still remain valid.

If X,Y ⊂ R n are tropical varieties, and p ∈ X ∩ Y , then we say that X and Y intersect transversally at p if p is contained in a face σ of X and in a face τ of Y such that the affine span of σ ∪ τ is equal to R n . We say that X and Y intersect transverally if X and Y intersect transverally at every intersection point. The fact that in our case X and Y intersect transversally is very important to our proof, and is given by the following result.

Lemma 2. If w is tropically generic, then X and Y intersect transversally at any of its intersection points.

Proof. Let p ∈ X ∩ Y . Let σ be a face of X and let τ be a face of Y , both containing p . Let L σ be the affine span of σ and let L τ be the affine span of τ . Then L σ contains zero, because zero is in the closure of every face of X . The translate L τ -w also contains zero, by the same reason. So, both L σ and L τ -w are vector spaces. Moreover, both vector spaces are defined over Q . Let W := L σ +( L τ -w ). Since p ∈ L σ and -p ∈ L τ , it follows that w ∈ W . But w is generic, and W is defined over Q . It follows that W = R n , which means X and Y intersect transversally.

As a consequence of transversality, it follows from [16, 3.4.12] that the tropicalization of the generic fiber is defined by the constraints we gave before Lemma 1.

Corollary 1. The tropicalization of the generic fiber C is equal to the intersection of X and Y (as a set).

Tropical varieties are defined as weighted polyhedral complexes, i.e., the maximal faces may come with higher multiplicity. Corollary 1 does not exclude multiple edges, but we will see in the next subsection that they will not occur.

## 2.2 Tropical Smoothness

For our discussion, we know by Sard's theorem that the generic fiber is smooth and with the help of the following lemma we also show that the corresponding tropical curve is smooth as well.

Lemma 3. Let G be a 1-dof graph, and let C be its generic fiber. Then the tropicalization Trop ( C ) is a smooth tropical curve.

Proof. Recall that we may consider Trop( C ) as being defined by the conditions

$$u _ { 0 } = 0$$

For all cycles C in G, min e ∈ C { u e } and min e ∈ C { w e -u e } are attained twice.

This can further be considered as the intersection of the two tropical varieties X and Y defined by

$$& X = \left \{ \underline { u } \in \mathbb { R } ^ { | E | - 1 } \, \colon \text{for all cycles $C$ in $G$,} \, \min _ { e \in C } \{ u _ { e } \} \, \text{is attained twice} \right \} \\ & Y = \left \{ \underline { u } \in \mathbb { R } ^ { | E | - 1 } \, \colon \text{for all cycles $C$ in $G$,} \, \min _ { e \in C } \{ w _ { e } - u _ { e } \} \, \text{is attained twice} \right \}.$$

A main observation is that Y is the image of X after reflection in each coordinate axis ( u → -u ) and translation by the weight vector w = ( w , ..., w 1 n ). In order to prove that V is smooth, we will use the following proposition [16, Theorem 3.4.12].

Proposition 1. Let W 1 and W 2 be subvarieties of ( C {{ }} t ∗ ) n . If the two tropical varieties Trop ( W 1 ) and Trop ( W 2 ) intersect transversally, then we have

$$T r o p ( W _ { 1 } ) \cap T r o p ( W _ { 2 } ) = T r o p ( W _ { 1 } \cap W _ { 2 } ).$$

Therefore, as long as two tropical varieties intersect transversally, their intersection is equal to the tropicalization of the intersection of the two algebraic varieties. Recall that in our case, the tropical variety X is the tropicalization of the linear variety L 1 defined as

$$L _ { 1 } \coloneqq \left \{ \underline { s } \in ( \mathbb { C } \{ \{ t \} \} ^ { * } ) ^ { n } \, \colon \text{for all cycles $C$ in $G$, $\sum_{e\in C}s_{e}=0$} \right \}.$$

The idea of our proof will be to show that for each point p ∈ Trop( C ), locally around p , Trop( C ) can be described as the transverse intersection of the tropicalization of two linear varieties which intersect in a line; therefore by Proposition 1, Trop( C ) is a tropical line locally around p , and is therefore smooth.

The two tropical varieties X and Y can also be considered as polyhedral complexes; by the genericity of the fiber, we may assume that no two codimension one faces of these complexes intersect. Therefore, a point p ∈ X ∩ Y is in one of the following three classes:

- 1. p lies in the intersection of a full dimensional face of X and a full dimensional face of Y .
- 2. p lies in the intersection of a codimension one face of X and a full dimensional face of Y .
- 3. p lies in the intersection of a full dimensional face of X and a codimension one face of Y .

↦

We now make a further reduction; we note that via the map u → w -u , which is a tropical isomorphism, we may interchange X and Y . This allows us to reduce to only Cases 1 and 2, by implicitly applying this isomorphism to any Case 3 occurrence, changing it to Case 2.

In both cases, we take some small neighbourhood U p of p . We will reflect, pointwise, all of Y through the point p -let us call this map σ . Note that this is a tropical isomorphism, and in particular U p ∩ Y = U p ∩ σ Y ( ). Therefore the intersection U p ∩ X ∩ Y is exactly U p ∩ X ∩ σ Y ( ). Furthermore, we know that σ Y ( ) is simply a translation of X , and so both are tropicalizations of the linear spaces X = Trop( L 1 ), σ Y ( ) = Trop( L ), for some linear space L . Since this intersection is transverse by Prop 1, we have that X ∩ σ Y ( ) = Trop( L 1 ∩ L ), which is the tropicalization of a line, as needed. This concludes the proof of Lemma 3.

As both the algebraic curve C and its tropical counterpart Trop( C ) are smooth, we obtain the following corollary as a consequence of Theorem 1. We will abuse notation and let C now refer to any single irreducible component of the generic fiber.

Corollary 2. Let C be an irreducible component of the generic fiber with respect to a 1-dof graph G , and let T be its tropicalization. Then the genus of C is equal to the tropical genus of T .

Now that we have proven the theoretical foundation for our result, we give an algorithm which explicitly calculates g (Trop( C )).

## 3 Algorithm

In this section we describe an algorithm for computing g (Trop( C )). As mentioned previously, the algorithm will calculate the number of bounded edges and vertices of the tropical curve Trop( C ) by traversing the curve iteratively. The input of the algorithm are the edges of the graph G , and the output is the value | E | - | V | +1, where E and V refer to the bounded edges and vertices of Trop( C ).

The first step of the algorithm is to find a good 'starting point', meaning a point on Trop( C ), such that this particular curve exhibits the properties we need - namely, it is a transverse intersection of the corresponding X and Y from the preceding section. In particular, this entails finding a point p ∈ R | E |-1 such that for a 'good' choice of weight vector w , the point p lies on the tropical curve Trop( C ); specifically, this means that p := ( x , ..., x 1 d ) (here indices correspond to edges of G ) satisfies the cycle conditions of the form min e ∈ C { x e } obtained twice, and that for some weight vector w = ( w , ..., w 1 e ) the cycle conditions min e ∈ C { w e -x e } obtained twice are also satisfied, and that furthermore this weight vector w gives a transverse intersection of the complexes X and Y as defined in Section 2.

After the starting point is found, the main algorithm begins. The basic structure is shown in Algorithm 1. Within Algorithm 1, there are two sub-routines, Directions( v ) and Travel( v, d ). The travel subroutine is simple, and moves in direction d from v until it reaches a vertex. The more complex subroutine is Directions( v ), which calculates the directions of the edges leaving v , together with the distance required to travel in each direction to find the next vertex. This is the content of Lemma 5, and the method used by the algorithm can be seen in Algorithm 2.

## 3.1 Starting Point / Weight Generation

Recall that Lemma 2 guarantees that if we take a generic weight vector, then any point in the tropical fiber of w determined by the tropical constraints given before Lemma 1 is a good starting point. But solving these contraints may be costly. In this subsection we explain how to avoid that costly step.

Lemma 4. Let u ∈ R n be a generic weight vector, and X be the tropical variety as defined in Lemma 3. Let p ∈ R n be the unique intersection point of X , the translate u + X , and the hyperplane H defined by x n -1 = 0 . If w := 2 p -u , then w is a generic weight vector, and p is a point in the intersection of X and Y := w -X .

Proof. Since p ∈ X ∩ ( u + X ) and Y = 2 p -( u + X ), it follows that p ∈ X ∩ Y , and the last claim is proved. Note that X and u + X intersect transversally at p , because u is generic. Because dim( X ) + dim( u + X ) + dim( H ) = n , the point p lies in a maximal faces of X u , + X , and H (the hyperplane H has only a single face anyway). So, there exists a neighborhood U of p ∈ R n such that U ∩ ( u + X ) is affine linear. Without loss of generality, the neighborhood of U may be assumed

̸

```
Algorithm 1 Traversing a Tropical Curve
    Unexplored = {Starting Point}
    Vertices = {Starting Point}
    Edges = { }
    while Unexplored \ 0 do
        for v \ in Unexplored do
              D = Directions(v)
              for d \ in D do
                  if (v, d) gives infinite ray then
                        Continue
                  end if
                  v' = Travel(v, d)
                  if v' \ Vertices then
                        Vertices = Vertices \ \ {v'}
                        Edges = Edges \ \ {v, v'}
                        Unexplored = Unexplored \ \ {v'}
                  end if
              end for
              Unexplored = Unexplored \ \ {v}
        end for
    end while
    return |Edges| - |Vertices| + 1
```

to be symmetric around p , i.e., U = 2 p -U . Then the tropical isomorphism t : z → 2 p -z maps u + X to Y . This implies that X and Y intersect transversally at p .

Let E ⊇ Q be the field generated by the coordinates of w . Then both X and Y are defined over E , and therefore the coordinates of p all lie in E . Then also the coordinates of u = 2 p -w also lie in E . But u was chosen generically, hence dim Q ( E ) = n . This shows the remaining claim that w is generic.

Our algorithm is probabilistic, with a single random step: the choice of a random vector u that plays the role of the generic translation from X to u + X . The conclusion in Lemma 4 is fulfilled with U in some open subset W ⊂ R n that contains all generic vectors. Its complement F is again a tropical variety of dimension less than n (see [16, Example 5.5.5]). Our probabilistic algorithm relies on the fact that a rational random vector will likely not lie in F .

Typically, the tropicalization of an algebraic system of equations is simpler than the variety itself. Linear systems are an exception to this rule of thumb. The tropical system for the starting point p is the tropicalization of the following linear system defined over C { } t :

$$\sum _ { e \in C } s _ { i } = \sum _ { e \in C } t _ { i } = 0 \text{ for all cycles } C, \ s _ { i } t _ { i } = t ^ { u _ { i } }, \ s _ { 0 } = t _ { 0 } = 1, \ s _ { n } = t ^ { 1 }.$$

In order to compute p , we solve this linear system and set p as the value vector of the unique solution. Since this requires Puiseux series arithmetic, this algorithm is implemented in Maple instead of Python.

## 3.2 Direction Calculation

A main step of our algorithm is to calculate the directions in which a tropical curve can continue from a vertex; in order to do this efficiently, we prove the following lemma restricting our search space to only the vectors with entries from { 0 1 , } .

Lemma 5. Let G be a 1-dof graph, and let B be an edge in the tropical curve Trop ( C ) , where the weights w e are integers. Then the direction vector of B is, up to scalar multiplication, a two-valued vector with entries in { 0 1 , } .

̸

Proof. Take any edge B of Trop( C ) ⊆ R d , and take a point x = ( x , ..., x 1 d ) in the interior of this edge (note that the indices here also correspond to some edge e = { 1 2 , } . On this edge, some coordinate entries may be constant; we assume that for those entries which are not constant, that they take a non-integer value, and are not equal to any value of the constant entries - this can be achieved by moving a small amount on the edge. We then define

$$\lceil x \rceil \coloneqq \left ( \lceil x _ { 1 } \rceil, \dots, \lceil x _ { d } \rceil \right ), \ \lceil x \rfloor \coloneqq \left ( \lceil x _ { 1 } \rfloor, \dots, \lceil x _ { d } \rceil \right ).$$

Both of these points lie on Trop( C ), since whichever value the minimum in any cycle condition min e ∈ C { x e } takes, after taking floor functions the two (or more) edges where the minimum is attained, still attain the minimum. The same is true of the other cycle condition min e ∈ C { w e -⌊ x e ⌋} , with the same argument applied to ⌊ w e -x e ⌋ = w e -⌊ x e ⌋ , which holds since w e is an integer.

We now claim that for sufficiently small λ 0 , the line segment

$$x + \lambda ( \lceil x \rceil - \lfloor x \rfloor ), \ \lambda \in ( - \lambda _ { 0 }, \lambda _ { 0 } )$$

is contained in Trop( C ). Indeed, we firstly note that at x , each cycle condition minimum is either being attained at an integer value, in which case since this line segment does not change the value of integer coordinates, the minimum is still being attained for λ small enough. Secondly, if the minimum in some cycle condition at x is being attained at a non-integer value, then all entries of x with that non-integer value are being changed by value λ (1 , 1 , ..., 1), and thus the minimum is preserved for small enough λ (we must ensure that none of these non-integer values are changed enough to become integers, since at these points they may become equal to the non-changing integer valued coordinates). Since the direction vector ⌈ x ⌉ - ⌊ x ⌋ has entries in { 0 1 , } , we are done.

Remark 2. We remark that when we explicitly calculate the direction vector of an edge, it may of course need to be scaled by some non-zero constant to have all non-zero entries equal to one. Therefore when we find the directions from a vertex, we must attempt to travel in both directions; we have lost the orientation of the direction by the rescaling implicitly involved.

We can further restrict our search space by checking, for a vertex v , in which positions each cycle minimum is obtained twice. This is useful since it allows us to 'connect together' coordinates, since some possible directions will break the minimum obtained twice condition. More precisely, suppose that at a vertex v = ( v , ..., v 1 d ), some cycle condition has its minimum being attained exactly twice, say at the coordinates ( v , v s t ). Then for any edge coming out of v , if the coordinate for v s is changing along that edge, the coordinate for v t must be changing by the same amount otherwise one would overtake the other, and the minimum would not be attained twice. We use the simple example of C 4 to illustrate this.

For the graph C 4 , with weights w 1 = 1 , w 2 = 2 , w 3 = 3, the two cycle conditions are

$$\min \{ x, y, z, 0 \} & \text{attained twice} \\ \min \{ 1 - x, 2 - y, 3 - z, 0 \} & \text{attained twice}$$

$$\min \{ 1 - x, 2 - y, 3 - z, 0 \} \, a t t a$$

Suppose that at some stage of the algorithm we are at the vertex (0 2 3) of the tropical curve in , , R 3 . From the first cycle condition, we see that the value of x cannot change; this would break the minimum condition. From the second cycle condition, we see that if either of y or z were to decrease, then the other one must remain fixed. Finally, we see that if either of y or z were to increase, then so must the other, by the same amount. This means that only three directions are possible; they are (0 , 1 1), (0 , , -1 0), and (0 0 , , , -1). These are precisely the three direction vectors of the edges coming out of this vertex. Below is an outline of the algorithm, written in pseudocode.

Algorithm 2 Calculation of possible directions from a vertex v Input: Vertex v and the set Equations of cycle equations Equations Pairs = { } for eq ∈ Equations do if v attains eq min exactly twice, at entries v , v i i then Pairs = Pairs ∪ {{ v , v i j }} end if end for Blocks = Transitive closure of Pairs Directions = 0,1 vectors with constant entries along each block in Blocks

## 4 The Genus of a Trace

In [6], the authors ask for the genus of the trace of a vertex of a 1-dof graph when an edge of the graph is fixed in position. The trace of a vertex is simply the projection of the configuration set to the coordinates of that vertex. The trace might be a finite set of points; this happens in the case when the fixed edge and the tracing point are contained in a rigid subgraph. If the trace has dimension one, then its irreducible components are curves that all have the same genus. Any irreducible component of the configuration set projects to an irreducible component of the trace. Since the genus never increases along an algebraic map between two algebraic curves, it follows that the genus of an irreducible component of the configuration set is an upper bound. Also, the upper bound is an equality if the projection map, restricted to one of the components, is birational to the image.

Throughout this section, we assume that G is a 1-dof graph, i, j, k are three distinct vertices, the fixed edge is { i, j } , and the tracing vertex is k . The graph G ′ obtained by adding edges { i, k } and { j, k } is called the extended graph G ′ . Since the edge lengths of { i, k } and { j, k } may be considered as local coordinates of the tracing vertex, the tracing set is finite if and only if both edge lengths have only finite values in the configuration set. This is the case if and only if the extended graph G ′ is not rigid. From now on, we assume that the tracing set has dimension one, or equivalently that the extended graph G ′ is rigid.

Following [9], we say that a graph is globally rigid if, for a generic realisation, all other realisations with the same edge lengths can be obtained by rotation or reflection.

Proposition 2. Assume that the extended graph G ′ is globally rigid. Then the projection map from the configuration set to the tracing set is generically injective. In particular, the restriction to any irreducible component is birational to its image.

Proof. Let K be the configuration set for fixed generic edge lengths of the graph G and fixed vertices i, j . Let p k be a generic point of the tracing set. Together with the lengths of { i, k } and { j, k } , the

fixed edge lengths form an edge length vector of G ′ that is generic in the image of the edge map. If G ′ is globally rigid, there are exactly two realisations of G ′ with this edge length vector and fixed vertices i, j . Moreover, one realisation is a reflection of the other. So, only one of them maps the vertex k to the position p k . This is then the only point in the preimage of p k under the projection map.

Figure 6 shows the trace of a vertex of a graph with 6 vertices such that the extended graph is globally rigid. The genus of the configuration sets and the traces can be computed using Algorithm 1.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-d8f2708c-e1e1-4f76-ba31-5fefa49d2b56.jpg)

Figure 6: Three traces of the same graph with six vertices. The genus of the configuration curves and the traces is equal to 17.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-ae38a3f1-2aee-46de-9aa2-b6a6e4607508.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-7e212469-cc2d-4604-906f-ccc171a579dc.jpg)

If the extended graph G ′ is not globally rigid, then it is sometimes possible to replace the graph G by a graph with fewer vertices that produces the same tracing set for k . For instance, if G is a 4-cycle, then the tracing set is a circle, and this circle can also be obtained by a subgraph with three vertices. We call such a process a simplification.

Definition 2 (Simplifications) . We define two types of simplifications.

- 1. Assume that H is a (minimally) rigid subgraph of G with two vertices u, v ∈ V ( H ) such that any edge of G connecting a vertex in V ( G ) \ V ( H ) with a vertex in V ( H ), then the vertex in V ( H ) is either u or v ; moreover, we assume that that V ( H ) \{ u, v } does not contain i , j , or k . Then the graph G 1 (which will be a 1-dof graph) obtained from G by replacing the subgraph H by a single edge { u, v } is called a simplification of the first kind .
- 2. Assume that G 2 is a proper 1-dof subgraph of G such that i, j, k ∈ V ( G 1 ). Then G 2 is called a simplification of the second kind .

If G 1 is a simplification of the first kind, then the tracing set of G is the union of the tracing sets of G 1 for different edge lenths of the new edge { u, v } . If G 2 is a simplification of the second kind, then the tracing set of G is a subset of the tracing set of G 1 . In both cases, any component of the tracing set of G is a component of a tracing set of the simplification.

It is known that global rigidity is preserved under 1-extensions and edge additions [9].

A graph is called 3-connected iff it has at least four vertices, and any subgraph obtained by removing two vertices is connected. A graph is called redundantly rigid if any subgraph obtained by removing an edge is rigid. By [9, Theorem 7.1], a graph with at least four vertices is globally rigid if and only if it is 3-connected and redundantly rigid. We also recall the theorem of Geiringer/Laman ([15, 12]): a graph H such that | E H ( ) | = 2 | V ( H ) | -3 is minimally rigid if and only if | E H ( ′ ) | ≤ 2 | V ( H ′ ) | -3 for every subgraph H ′ of H with at least two vertices.

Lemma 6. Let H by a rigid graph such that | E H ( ) | = 2 | V ( H ) | -2 that is not redundantly rigid. Then H has a proper rigid subgraph H 1 such that | E H ( 1 ) | = 2 | V ( H 1 ) | -2 .

Proof. Let e ∈ E H ( ) such that the graph H 0 obtained from H by removing e is not rigid. Then | E H ( 0 ) | = 2 | V ( H 0 ) | -3, and by the theorem of Geiringer/Laman there exists a subgraph H 1 of H 0 such that | E H ( 1 ) | &gt; 2 | V ( H 1 ) | -3. Let e ′ ∈ E H ( ) be an edge such that the graph H 2 obtained from H by removing e ′ is minimally rigid - such an edge exists because H is rigid but not minimally rigid. Let H 3 be the graph obtained from H 1 by removing e ′ in case e ′ ∈ E H ( 1 ), otherwise we set H 3 = H 1 . Then H 3 is a subgraph of H 2 , and | E H ( 3 ) | ≤ | 2 V ( H 3 ) |-3 by Geiringer/Laman. Therefore e ′ ∈ E H ( 1 ) and | E H ( 1 ) | = 2 | V ( H 1 ) | -2. Also, the graph H 3 is minimally rigid by Geiringer/Laman, and therefore H 1 is rigid as well.

Proposition 3. If the graph G ′ is not globally rigid, then there exists a simplification of the first or second kind.

Proof. By the theorem of Jackson/Jord`n, the graph a G ′ is not 3-connected or not redundantly rigid. We distinguish these two cases.

Case 1: G ′ is not 3-connected. Then there exist u, v ∈ V ( G ) such that the full subgraph of G ′ with vertex set V ( G ) -{ u, v } is not connected. From the connected components and the vertices u and v , we can form two proper subgraphs G , G 1 2 of G ′ such that E G ( ′ ) is the disjoint union of E G ( 1 ) and E G ( 2 ), and V ( G 1 ) ∩ V ( G 2 ) = { u, v } . At least one of G , G 1 2 is rigid, because otherwise G ′ could not be rigid, contrary to one of the assumptions in the beginning of this section. Without loss of generality, we assume that G 2 is rigid. Since the 3-cycle with vertices i, j, k is contained in G ′ , all its three vertices must either be all in G 1 or all in G 2 . They cannot be in G 2 because then the tracing set would be finite. Hence they are all in G 1 . And then G 1 minus the two edges { i, k } and { j, k } is a simplification of the first kind.

Case 2: G ′ is not redundantly rigid. If either { i, k } or { j, k } is already in G , then the trace is a circle, and the full subgraph with vertices i, j, k is a simplification of the second kind. Similarily, if G ′ minus the edge { i, k } is not rigid, then the trace is a circle, and we get a simplification as well. So we assume { i, k } and { j, k } are not in G and that the two graphs G ′ minus { i, k } and G ′ minus { j, k } are rigid; then the two graphs are necessarily minimally rigid. The first statement implies that | E G ( ′ ) = 2 | V ( G ′ ) | -2. By Lemma 6, G ′ has a rigid subgraph G 1 such that | E G ( 1 ) | = 2 | V ( G 1 ) | -2. By

Geiringer/Laman, G 1 cannot be a subgraph of ( G ′ minus { i, k } ). Hence { i, k } ∈ E G ( 1 ). Similarily, { j, k } ∈ E G ( 1 ). So, G 1 minus the two edges { i, k } and { j, k } is a simplification of the second kind.

Proposition 2 and Proposition 3 together imply that the genus of a component of a trace is equal to the genus of a component of the configuration curve, after fully simplifying the graph (meaning repeatedly finding simplifications until the extended graph is globally rigid). Hence we can use Algorithm 1 for computing the genus of a trace.

## 5 Examples

In this section we give a fully worked example for C 4 , and then give the genus of the generic configuration space for various other graphs. For the family of graphs K 2 ,n we prove a formula for the genus using the Riemann-Hurwitz formula, and show that it agrees with our computations.

## 5.1 The graph C 4

In the case of the four-cycle C 4 , we normalise the edge variables s 0 = t 0 = 1, and after picking generic positive valuation Puiseux series λ , λ 1 2 , λ 3 , the generic fiber for the edge map f C 4 is the set of ( s , s 1 2 , s 3 , t 1 , t 2 , t 3 ) ∈ ( C {{ }} t ∗ ) 6 that satisfy the conditions

$$s _ { 1 } t _ { 1 } = \lambda _ { 1 }, \quad s _ { 2 } t _ { 2 } = \lambda _ { 2 }, \quad s _ { 3 } t _ { 3 } = \lambda _ { 3 } \\ 1 + s _ { 1 } + s _ { 2 } + s _ { 3 } = 0, \quad 1 + t _ { 1 } + t _ { 2 } + t _ { 3 } = 0.$$

After tropicalization, these equations become

$$u _ { 0 } = v _ { 0 } = 0, \ \ u _ { 1 } + v _ { 1 } = w _ { 1 }, \ \ u _ { 2 } + v _ { 2 } = w _ { 2 }, \ \ u _ { 3 } + v _ { 3 } = w _ { 3 }$$

$$u _ { 0 } = v _ { 0 } = 0, \quad u _ { 1 } + v _ { 1 } = w _ { 1 }, \quad u _ { 2 } + v _ { 2 } = w _ { 2 }, \quad u _ { 3 } + v _ { 3 } = w _ { 3 } \\ \min \{ 0, u _ { 1 }, u _ { 2 }, u _ { 3 } \} \text{ occurs twice}, \quad \min \{ 0, v _ { 1 }, v _ { 2 }, v _ { 3 } \} \text{ occurs twice}.$$

Finally, after using the first three equations to eliminate the v variables, we find the two tropical varieties X and Y as in Section 2. We rename the three remaining variables to x, y, z for convenience.

$$X \coloneqq \left \{ ( x, y, z ) \in \mathbb { R } ^ { 3 } \, \colon \min \{ 0, x, y, z \} \, \text{occurs twice} \right \} \\ Y \coloneqq \left \{ ( x, y, z ) \in \mathbb { R } ^ { 3 } \, \colon \min \{ 0, w _ { 1 } - x, w _ { 2 } - y, w _ { 3 } - z \} \, \text{occurs twice} \right \}.$$

The tropical curve we are interested in is the intersection of these two polyhedral complexes. They are shown below, together with their intersection.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-e28755ed-bea2-47fc-ae8b-4febf2182e54.jpg)

Figure 7: The Polyhedral Complex X

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-e53e4c7d-9b7f-47b6-9487-7bd86148299e.jpg)

Figure 8: The Polyhedral Complex Y

Figure 9: The tropical curve X ∩ Y corresponding to C 4

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-1b8a4038-b094-46d7-a7f9-6f77b9b5cf1d.jpg)

We see from Figure 9 that the underlying graph of X ∩ Y is C 6 , which has Betti number one, confirming that the graph C 4 has generic fiber of genus one.

## 5.2 The Bipartite Graphs K 2 ,m

Generalising the example C 4 = K 2 2 , above, we can use our algorithm to calculate the genus of the generic fiber for the bipartite graphs K 2 ,m , for m up to 11. The values are shown below.

Table 1: The genus of the bipartite graphs K 2 ,m calculated by the algorithm.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-19b83082-feb6-497b-b800-469e462cb73b.jpg)

These values can be verified, and further a closed form for the genus g K ( 2 ,m ) can be given by using the Riemann-Hurwitz formula. Let C K 2 ,m denote the curve given by the generic fiber of K 2 ,m , and we consider K 2 ,m as being obtained by a single Henneberg 1-move (also called a 0extension) from K 2 ,m -1 , which creates the new vertex w = ( z , z 1 2 ). Applying Riemann-Hurwitz to the projection

↦

$$\pi \colon C _ { K _ { 2, m } } \to C _ { K _ { 2, m - 1 } }, ( x _ { 1 }, y _ { 1 }, \dots, x _ { m - 1 }, y _ { m - 1 }, z _ { 1 }, z _ { 2 } ) \mapsto ( x _ { 1 }, y _ { 1 }, \dots, x _ { m - 1 }, y _ { m - 1 } )$$

we see that this is a branched covering of degree 2, whose ramification points correspond to realisations of K 2 ,m where the new vertex w is collinear with its neighbours v 1 and v 2 . Such realisations occur in two scenarios:

$$d ( v _ { 1 }, v _ { 2 } ) ^ { 2 } = ( d ( v _ { 1 }, w ) + d ( w, v _ { 2 } ) ) ^ { 2 }, \ \ d ( v _ { 1 }, v _ { 2 } ) ^ { 2 } = ( d ( v _ { 1 }, w ) - d ( w, v _ { 2 } ) ) ^ { 2 }$$

which gives two possible values for the squared distance between v 1 and v 2 . The number of times one of these equations is satisfied in K 2 ,m is the realisation number of the graph K 2 ,m ∪ { v , v 1 2 } , where the squared distance between v 1 and v 2 is chosen as the one being tested for. This graph is a collection of m triangles with a common edge; however the triangle containing w is degenerate (by the collinearity of v 1 , v 2 , and w ), and therefore this graph has realisation number 2 m -1 . Doing this for each of the two possible squared distance, we find that the number of ramification points is 2 m . The Riemann-Hurwitz formula then gives

$$2 g ( C _ { K _ { 2, m } } ) - 2 = 2 ( 2 g ( C _ { K _ { 2, m - 1 } } ) - 2 ) + 2 ^ { m }.$$

Solving this recurrence gives the closed form

$$g ( C _ { K _ { 2, m } } ) = ( m - 2 ) 2 ^ { m - 1 } + 1$$

which agrees with the calculated values in Table 1.

Remark 3. The graphs K 2 ,m , m ≥ 2 fit into a larger, two parameter family of graphs O l,r , where the graph O l,r is obtained from the four cycle K 2 2 , by performing l 0-extensions on the two 'left' vertices of the partition, and r 0-extensions on the two 'right' vertices of the partition. Note that it is irrelevant in which order these extensions are performed, and that O l,r is a bipartite graph with 4 + l + r vertices. The graphs K 2 ,m are the subfamily of graphs O m -2 0 , .

An almost identical application of Riemann-Hurwitz to the above, shows that the behaviour of the genus of these graphs is independent of the side on which the 0-extension is performed; that is, we have

$$g ( C _ { O _ { l, r } } ) = g ( C _ { O _ { l - 1, r + 1 } } ) = \dots = g ( C _ { K _ { 2, l + r + 2 } } ).$$

## 5.3 Further Examples

Using our algorithm, we have calculated the genus for various graphs. Below is a list of graphs together with their genus. Note that we do not list 1-dof graphs which are simply a smaller 1-dof graph with a rigid part attached along an edge, such as the C 4 with a triangle on one of its edges. A rigid graph R attached to an edge of a 1-dof graph does not change the genus of (a simple component of) the generic fiber - this can be seen by applying Riemann-Hurwitz to the projection which removes R -this map has degree 1 with no branching points, when applied to a single component of the generic configuration space of the larger graph.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-97727b6e-fee6-4625-bc1d-7366eacda989.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-39ad69b6-be3a-4173-a604-d657e1e488c8.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-afaa5de9-2694-439b-8047-11838eb2d716.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-d139d6cc-616a-4e65-a69c-807b8b5f4067.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-0fd8df28-ed3d-4fde-83f4-7a2d95a654b2.jpg)

Genus 129

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-aec45737-de3c-48f0-87a8-6104a0628b34.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-ee0130c6-49ef-48d5-8832-f259892feb19.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-bcd1c057-ccf8-4632-93ef-81d8ae747794.jpg)

Genus 225

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-ab4d1189-92a7-4903-b3c2-3dc11347f9e3.jpg)

Genus 247

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-5ee675f3-aeb8-4098-920b-d1c40bdac285.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-199c3534-c4e7-4b86-ac0b-3a553ec3fa65.jpg)

Genus 795

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-89094030-2667-4713-b029-974621f3e53e.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-55f9d50e-9292-405d-8780-1e08f1069a0d.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-93fc070b-9082-4292-8d71-81d3bb1a819a.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-c48ae6dc-96d2-4d74-a0da-7fc4901693bd.jpg)

In addition to the genus, the code outputs an image of the tropical curve, with the infinite rays removed. Some example images are shown below.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-802d80d9-1ff3-440e-a3e0-6dca90979c59.jpg)

As a concluding remark, we observe that for all examples we computed above, the genus of the configuration space is odd. It seems reasonable to conjecture that for all 1-dof graphs, the configuration space for generic edge lengths has odd (or zero) genus.

This does not contradict Kempe's universality theorem, which states that any algebraic curve in the plane is the trace of a vertex of some graph. If we would give a plane algebraic curve of even genus, our results in Section 4 would imply that it cannot be the trace of a generic 1-dof graph -otherwise after simplifying we would find a (generic) 1-dof graph with configuration set of even genus. This is not a contradition with the conjecture, rather it implies that such traces are given by non-generic configuration sets of graphs.

Figure 10: The tropical curve of the Wagner graph Genus 225

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00449v2-figure-dfb2051b-6c30-4883-86af-bf631ef0eb83.jpg)

## Acknowledgements

The authors would like to thank Jan Legersk´, Matteo Gallet, and many guests of the RICAM y Special Semester on Rigidity and Flexibility for helpful conversations.

Research Institute for Symbolic Computation (RISC) Johannes Kepler University, Linz, Austria josef.schicho@risc.jku.at

Johann Radon Institute for Computational and Applied Mathematics (RICAM)

Austrian Academy of Sciences, Linz, Austria ayushkumar.tewari@ricam.oeaw.ac.at audie.warren@oeaw.ac.at

## References

- [1] F. Babaee, S. Dewar, and J. Maxwell. Extremal decompositions of tropical varieties and relations with rigidity theory. arXiv Preprints: 2403.00655 , 2024.
- [2] V. G. Berkovich. Spectral theory and analytic geometry over non-Archimedean fields , volume 33 of Mathematical Surveys and Monographs . American Mathematical Society, Providence, RI, 1990.
- [3] D. Bernstein and R. Krone. The tropical Cayley-Menger variety. SIAM J. Discr. Math. , 33:1725-1742, 2019.
- [4] C. Borcea and I. Streinu. The number of embeddings of minimally rigid graphs. Discrete &amp; Computational Geometry , 31(2):287-303, Feb 2004.
- [5] J. Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, and J. Schicho. The number of realizations of a Laman graph. SIAM Journal on Applied Algebra and Geometry , 2(1):94-125, 2018.
- [6] G. Grasegger, B. El Hilany, and N. Lubbes. Coupler curves of moving graphs and counting realizations of rigid graphs. Math. Comp. , 93:459-504, 2024.
- [7] G. Grasegger, J. Legersk´, and J. Schicho. y Graphs with flexible labelings allowing injective realizations. Discrete Mathematics , 343(6):111713, 2020.
- [8] I. Izmestiev. Four-bar linkages, elliptic functions, and flexible polyhedra. Comp. Aided Geom. Design , 79, 2020.
- [9] B. Jackson and T. Jord´n. a Connected rigidity matroids and unique realisations of graphs. J. Comb. Theory B , 94:1-24, 2005.
- [10] B. Jackson and J. Owen. Equivalent realisations of a rigid graph. Discrete Applied Mathematics , 256:42-85, 2019.
- [11] P. Jell. Constructing smooth and fully faithful tropicalizations for Mumford curves. Selecta Mathematica , 26(4):60, 2020.
- [12] G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics , 4:331-340, 1970.
- [13] N. Lubbes, M. Makhul, J. Schicho, and A. Warren. Irreducible components of sets of points in the plane that satisfy distance conditions. arXiv Preprints: 2403.00392 , 2024.
- [14] G. Mikhalkin and J. Rau. Tropical Geometry . Textbook in Preparation.
- [15] H. Pollaczek-Geiringer. ¨ ber U die Gliederung ebener Fachwerke. Zeitschrift f¨r u Angewandte Mathematik und Mechanik (ZAMM) , 7:58-72, 1927.

- [16] B. Sturmfels and D. Maclagan. Introduction to Tropical Geometry . American Mathematical Society, 2015.
Josef Schicho Ayush Kumar Tewari Audie Warren
On the Genus of One Degree of Freedom Planar Linkages via Tropical Geometry
This paper focuses on studying the configuration spaces of graphs realised in
$\mathbb C^2$, such that the configuration space is, after normalisation, one
dimensional. If this is the case, then the configuration space is, generically,
a smooth complex curve, and can be seen as a Riemann surface. The property of
interest in this paper is the genus of this curve. Using tropical geometry, we
give an algorithm to compute this genus. We provide an implementation in Python
and give various examples.