Evangelos Bartzos
email: vbartzos@di.uoa.gr

Ioannis Z Emiris
email: emiris@di.uoa.gr

Charalambos Tzamos
email: ctzamos@di.uoa.gr

An Asymptotic Upper Bound For Graph Embeddings 1

Keywords: Graph embedding, Graph orientation, Minimally rigid graph, Laman graph, Upper bound 24

We address a central question in rigidity theory, namely to bound the number of Euclidean or spherical 7 embeddings of minimally rigid graphs. Since these embeddings correspond to the real roots of certain 8 algebraic systems, the same enumerative question can be asked in complex spaces. Bézout's bound on 9 the quadratic equations that capture the edge lengths yields trivially a bound of O 2 d•|V | embeddings, 10 for graphs of |V | vertices in d dimensions; it had not been improved until recently. A first improvement 11 was obtained for d ≥ 5 [4]. The same work related the number of embeddings and the number of a class 12 of graph orientations. A combinatorial analysis based on the latter yielded the first nontrivial upper 13 bounds for 2 ≤ d ≤ 4, while further improving the bounds for d ≥ 5 [6]. 14 Here, we follow a similar procedure as in [6]. First we obtain upper bounds on graph orientations 15 with fixed outdegree by enhancing the existing graph theoretic tools. Then we use the relation between 16 graph orientations and the bound on the embedding number to provide provide new upper bounds in all 17 dimensions on the number of complex embeddings by extending the recent progress. Namely, for d = 2 18 (Laman graph embeddings) and d = 3, we improve the upper bound from O(3.78 |V | ) to O(3.46 |V | ) and 19 from O(6.84 |V | ) to O(6.32 |V | ), respectively. 20 Regarding the tightness of our results, we present examples of graphs indicating that our bound on 21 the outdegree-constrained orientations may be sharp, but we have no similar data for the embedding 22 number.

Introduction

25

Rigidity theory studies the properties of graphs that can have rigid embeddings in a specified embedding space.

26

Besides being a mathematical area with significant research interest, it has also received much attention due to its 27 applications in molecular biology [START_REF] Lavor | Minimal NMR distance 628 information for rigidity of protein graphs[END_REF], robotics [START_REF] Zelazo | Rigidity maintenance control for multi-638 robot systems[END_REF], and architecture [START_REF] Baglivo | Incidence and Symmetry in Design and Architecture[END_REF][START_REF] Emmerich | Structures Tendues et Autotendantes[END_REF].

28

Let G, be a simple undirected graph and R d be the embedding space. We will denote by V (G) and E(G) simple undirected graphs, these frameworks are called bar (or bar-joint) frameworks [START_REF] Schulze | Rigidity and scene analysis[END_REF]. Every framework induces 33 a bilabelled set of edge lengths λ = ( pupv ) (u,v)∈E , that are called bars. An embedding (and its corresponding 34 framework) is rigid if and only if it admits a finite number of embeddings that satisfy the edge lengths, up to rigid 35 motions; otherwise it is flexible. In fact, rigidity or flexibility is a generic property of the underlying graph, since 36 generically rigid graphs are rigid for any edge lengths induced by a generic embedding [START_REF] Asimow | The rigidity of graphs[END_REF]. We are particularly 37 interested in the class of generically minimally rigid graphs, that correspond to well-constrained algebraic systems. outdegree-constrained orientations of G ′ = (V, E \ E(K d ′ )), such that:

96

• the outdegree of vertices V (K d ′ ) is 0.

97

• if d ′ < d, then the outdegree of the partially fixed vertices v d ′ +1 , . . . v d is d ′ , . . . , d -1, respectively.

98

• the outdegree of every vertex in V \ (V (K d ′ ) ∪ V ′ ) is d.

99

Then the embedding number of G in C d , is bounded from above by the following quantity:

mBe(G, K d ′ , V ′ ) = 2 |V |-d • R(G, K d ′ , V ′ ).
The bound of this theorem is actually the multihomogeneous Bézout (m-Bézout) bound of an algebraic system, 100 whose number of solutions corresponds to the embedding number (see [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings 605 of minimally rigid graphs[END_REF] for details). In the case d = 2, there is 101 always a fixed edge K2, so V ′ = ∅. For Geiringer graphs, although in most known cases there exists at least one 102 triangle, there are graphs such as K6,4 with no such subgraph. When V ′ = ∅, we omit V ′ , and write mBe(G, K d ) 103 and R(G, K d ) to denote the bound of Theorem 1 and the number of the orientations, respectively. The outdegrees 104 in this theorem represent the number of coordinate variables per vertex in the underlying algebraic system [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF]. All 105 other coordinates are fixed.

106

This theorem relates the embedding number of a minimally rigid graph G and the number of its orientations.

107

Hence, bounding the number of orientations immediately yields bounds on the embedding number by applying 108 Theorem 1. In this work, we provide tighter upper bounds on the number of orientations, hence better upper bounds 109 on the embedding number, for the class of minimally rigid graphs. For this, following [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF], we use a graphical structure Let J = (VJ , EJ , HJ ) be a pseudograph. A sub-pseudograph of J, is a pseudograph formed by subsets of VJ , EJ , 115 and HJ . In the sequel, given a sub-pseudograph J ′ , we denote by V (J ′ ), E(J ′ ) and H(J ′ ) the vertices, the normal 116 edges and the hanging edges of J ′ respectively. We also denote by J[V ′ ] the sub-pseudograph induced by a subset 117 of vertices V ′ ⊆ VJ . Every vertex v of a pseudograph has a degree profile (r, h), where r denotes the number of the 118 normal edges that are incident to v, and h denotes the number of the hanging edges that are incident to v. Also, we 119 refer to r as the normal degree of v, and to h as the hanging degree of v. 1 The simple undirected graph J * = (VJ , EJ ) 120 is the normal subgraph of J.

v 1 v 2 v 3 v 4 v 5 v 3 v 4 v 5
Figure 1: A Laman graph and a pseudograph constructed after removal of a fixed K 2 . (left) Laman graph G, with fixed edge (v 1 , v 2 ) (dashed blue). Since the fixed vertices have outdegree 0, their incident edges (red) are uniquely oriented. (right) The corresponding pseudograph. The red arrows represent the hanging edges. The degree profiles for vertices v 3 , v 4 , v 5 are respectively (2, 2), (2, 1), (2, 0).

• J d has at least 2 vertices and no cycles,

141 • J -J d is connected, 142
• v0 is the leading vertex of J d . This is a non-cut vertex and it is always connected with other vertices in J -J d .

143

All the other vertices of J d are the non-leading vertices,

144

• all vertices have normal degree 2d -1, except possibly v0.

145 Sub-pseudographs J d are used to include path elimination steps in the elimination process. Path elimination steps 146 also appear in [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF], but here we use different paths that eventually improve the bound. The leading vertex of a J d is 147 the vertex that is the first to be removed, during the elimination of its corresponding sub-pseudograph J d .

148

Let us now give a detailed description of the elimination process for a connected d-pseudograph. The process 149 consists of elimination steps, in which vertices are removed in a controlled manner, resulting to smaller pseudographs.

150

There are two types of elimination steps: This process has the following stopping condition, already used in [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF]Prop.3.7].

168 Lemma 5 ([6]). Let J = (VJ , EJ , HJ ) be a pseudograph such that its normal subgraph J * = (VJ , EJ ) is a tree.

174

In order to restrict the parameters of the bound in our analysis only to total number of vertices and hanging edges,

175
we prefer to keep the pseudograph connected throughout the elimination process.

176

Now we show that there is always an elimination process that does not create more connected components of the

183

We may use the same definition for the block-cut tree (see Figure 3) of the normal subgraph of every pseudograph. The following lemma uses Maxwell's condition and Definition 6 to bound the normal degree of the eliminated 185 vertices. 186 Lemma 7. Let J = (VJ , EJ , HJ ) be a connected d-pseudograph derived from a minimally rigid graph G, as described 187 above. Then J has at least one non-cut vertex with normal degree smaller than or equal to 2d -1.

184 v 0 v 2 v 1 B 1 B 2 B 3 B 4 B 1 v 0 l (v0,v2) v 2 B 4 B 2 v 1 B 3

188

Proof. Let J * = (VJ , EJ ) denote the normal subgraph of J. Since J * ⊆ G, Maxwell's condition holds for every

189 subgraph J ′ of J * , so we get that |E(J ′ )| ≤ d • |V (J ′ )| -d+1 2 .

225

The exact formulas for these quantities were given in [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF]Prop. 3.4] as follows:

226 Lemma 8 ([6]
). Let J be a d-pseudograph and v be one of its vertices with degree profile (r, h). The cost for the 227 elimination of a vertex v is denoted with C d (r, h) and is given by the formula:

228 C d (r, h) = r d -h , (1)
while the hanging edges equilibrium shall be denoted with H.E.E.:

229

H.E.E. = r -d (2)
Regarding the quantities we use for vertex removal, notice that while the cost depends both on the normal and 230 the hanging degree of a vertex, the H.E.E. depends only on the first one. This shall be used to group the elimination 231 of vertices with different hanging degree, but the same normal one, in the path elimination steps.

232

These general aspects of the elimination process were also used in [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF]. Now we will present some new clues and 233 concepts that will lead to the improved bounds eliminating sub-pseudographs J d (see Definition 4).

234

First, remark that there are different scenarios for the distribution of hanging edges in the neighbours of an 235 eliminated vertex v in the resulting graphs. Therefore, we will give an additional count that determines in how many 236 ways a neighbour of the eliminated vertex acquires a new hanging edge or not.

237

Lemma 9. Let v be an eliminated vertex with degree profile (r, h) and u be one of its neighbours in a d-pseudograph 238 J. Then there are exactly

239 r -1 d -h and r -1 d -h -1 (3)
ways in which u acquires, and does not acquire a hanging edge, respectively, after the elimination of v.

240

Proof. Let us consider that u gets a hanging edge after the elimination of v. That means that the edge e = (u, v)

241 is directed towards v, so dh edges incident to v shall be directed outwards it. The available edges after the 242 orientation of e are r -1, indicating that there are r -1 dh ways to orient them. Since the cost for the elimination

243 of v is r d -h
, by Pascal's identity we derive the count for the case that u does not get a hanging edge. The two hanging edges of this vertex shall be removed and the same shall happen for one of its normal edges. The remaining two edges will become hanging edges on their other endpoint. Therefore the cost is 3 3-2 = 3 and every neighbour acquires a hanging edge in 2 scenarios.

These quantities shall be used to determine the worst case scenarios for the vertices that are eventually eliminated 245 with different degree profiles.

246

Now we present the basic aspects of path elimination. Notice that path vertex elimination steps were also used 247 in [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF]. Here, we take a different approach and alter the method in order to group vertices of different hanging degree, 248 but same normal degree.

249

We denote by C d (ℓ) the cost for the elimination of a sub-pseudograph J d with ℓ + 1 ≥ 2 vertices. The leading 250 vertex v0 has a particular degree profile (r, h). We will consider principally the case that r = 2d -1, leading vertices 251 with different normal degree are considered only in Lemma 22. All the other vertices have the same normal degree, 252 2d -1, in J d before the elimination. Now, the elimination of J d can be seen as consecutive single vertex elimination 253 steps. Thus, after the elimination of v0, v1 has a drop in normal degree by 1 and will be eliminated as a vertex with 254 normal degree 2d -2. This will happen for all vertices in J d , but for v0. On the other hand, these vertices do not 255 have a standard hanging degree, since the distribution of hanging edges in the resulting pseudographs follows the 256 count of Lemma 9 (see Figures 5 and6 for examples).

257

In the analysis for the total cost of a pseudograph J, we separate the case of the leading vertex v0 with degree

C d (ℓ) C d (0) 1/ℓ
where C d (0) is the cost of the removal of v0. Moreover if there is an effective cost C * d (0) for C d (0), then the ratio

C d (ℓ) C * d (0)
C d (ℓ) C * d (0) 1/ℓ
as the cost for all the other vertices

272 in J d -{v0}, the total cost is remains C d (ℓ) = C * d (0) • C d (ℓ) C * d (0) 1/ℓ ℓ 2 .

273

In the sequel, we present some technical lemmas, defining certain sequences and a bound on them. The reason

B d (ℓ + 1) = α d 2 • (B d (ℓ) + G d (ℓ)) G d (ℓ + 1) = α d 2 • B d (ℓ) + β d - α d 2 • G d (ℓ) (4)
where

α d = 2d-2 d-1
and

β d = 2d-2 d
, and d ≥ 2.

278

Given these functions we define the sequence

279 C d (ℓ) = α d B d (ℓ) + β d G d (ℓ). (5)
Then C d (ℓ) is defined recursively for ℓ ≥ 1 by:

C d (ℓ + 1) = β d • C d (ℓ) + α d (α d -β d ) 2 • C d (ℓ -1) (6)
Proof.

C d (ℓ + 1) = α d B d (ℓ + 1) + β d G d (ℓ + 1) = α 2 d 2 (B d (ℓ) + G d (ℓ)) + α d β d 2 B d (ℓ) + β d (β d - α d 2 )G d (ℓ) = α 2 d 2 (α d B d (ℓ -1) + β d G d (ℓ -1)) + α d β d 2 (B d (ℓ) -G d (ℓ)) + β d (C d (ℓ) -α d B d (ℓ)) = α 2 d 2 C d (ℓ -1) + β d C d (ℓ) - α d β d 2 (B d (ℓ) + G d (ℓ)) = β d • C d (ℓ) + α d (α d -β d ) 2 • C d (ℓ -1)
D(d) = α 2 d + β 2 d α d + β d , given that B d (0) = G d (0) = 1. 286 2 Note that max 0≤h≤d C d (r, h
) is used as the effective cost to fit to the total cost analysis for single vertex elimination steps, that takes into account the biggest cost among vertices with the same normal degree (see Sections 3 and 4).

Proof. First, we will prove that it holds for ℓ ≥ 4, and then we will prove it for the 4 starting cases.

C d (ℓ + 1) C d (ℓ) ≤ α 2 d + β 2 d α d + β d ⇐⇒ (α d + β d ) • C d (ℓ + 1) ≤ (α 2 d + β 2 d ) • C d (ℓ) ⇐⇒ α d β d C d (ℓ) + β 2 d C d (ℓ) + α d (α d -β d )(α d + β d ) 2 • C d (ℓ -1) ≤ α 2 d C d (ℓ) + β 2 d C d (ℓ) ⇐⇒ (α d + β d ) • C d (ℓ -1) ≤ 2 • C d (ℓ) ⇐⇒ (7)
(α d + β d ) • C d (ℓ -1) ≤ 2β d • C d (ℓ -1) + α d (α d -β d ) • C d (ℓ -2) ⇐⇒ C d (ℓ -1) ≤ α d • C d (ℓ -2) ⇐⇒ (8)
β d • C d (ℓ -2) + α d (α d -β d ) 2 • C d (ℓ -3) ≤ α d • C d (ℓ -2) ⇐⇒ α d • C d (ℓ -3) ≤ 2 • C d (ℓ -2) ⇐⇒ (9)
α d • C d (ℓ -3) ≤ 2β d • C d (ℓ -3) + α d (α d -β d )C d (ℓ -4) ⇐⇒ (α d -2β d ) • C d (ℓ -3) ≤ α d (α d -β d ) • C d (ℓ -
C d (1) C d (0) = α 2 d + β 2 d α d + β d .
For the case of C d (2)/C d (1), we stop at the inequality (7) above, for ℓ = 1, and we have

(α d + β d ) • C d (0) ≤ 2 • C d (1) (α d + β d ) 2 ≤ 2 • (α 2 d + β 2 d ) (α d -β d ) 2 ≥ 0 which is true. 290 For the case C d (3)/C d (2)
, we stop at the inequality [START_REF] Blumenthal | Theory and Applications of Distance Geometry[END_REF], for ℓ = 2:

291 C d (1) ≤ α d • C d (0) α 2 d + β 2 d ≤ α 2 d + α d β d which is true, since α d ≥ β d .

292

For the last case, consider inequality (9) at ℓ = 3. We have that

α d • C d (0) ≤ 2 • C d (1)
α d β d ≤ α 2 d + 2β 2 d
which is clearly true.

293

Notice that setting B(0) = G(0) = 1, as stated above, we get C d (0) = α d + β d . Furthermore, using equations 4 and 6, we get C d (1) = α 2 d + β 2 d . Thus, lemma 12 clearly shows that the following inequality holds for the average cost of every sequence defined as in Lemma 11 with the given initial condition.

C d (ℓ) C d (0) 1/ℓ ≤ C d (1) C d (0) 1/ℓ , 3
Laman Graphs

294

In this section, we develop a method that improves the existing upper bounds on the embedding number of Laman 295 graphs, which are the minimally rigid graphs in dimension 2. The analysis for this dimension is simpler than the 296 ones regarding higher dimension and serves as base case for higher dimensions. Our method relies on Theorem 1,

297

which relates the bound on the embedding number with the outdegree-constrained orientations. In this section we 298 can remove subscripts referring to the embedding space from F d,J , J d , C d , α d , β d . Additionally, the leading vertex v0 299 for all paths J has only normal degree 3, that is exactly 2d -1 in the case of d = 2.

300

We use an elimination process similar to [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF] in order to improve the upper bound. We recall that the tree condition

303

One of the main differences between the elimination method described here and the one in [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF], is the restriction 304 on the normal degree of the eliminated vertices. Specializing Lemma 7 to the case of d = 2, we have that connected

312

The vertices that have cost equal to 1 will be called trivial vertices in the sequel, since their removal does not 313 increase the total cost of the elimination process.

314

Now we will describe the elimination process and the different cases treated. All vertices with normal degree 3 315 are eliminated with a single vertex elimination step, their cost is bounded by 3 and generate 1 hanging edge. For the 316 vertices with normal degree 2, we consider a dichotomy described in the following definition.

317

Definition 13. We consider a pseudograph J and an elimination process.The non-composite vertices with normal 318 degree 2 are the eliminated vertices that 319

• had already normal degree 2 in J.

320

• have normal degree 2 and they were generated by the removal of another non-composite trivial vertex with 321 normal degree 2 or by the removal of a vertex with normal degree 1.

322

All the other vertices eliminated with normal degree 2 are called composite.

323

Notice that since non-composite (2, 1) vertices have one hanging edge and the H.E.E. of trivial vertices that may 324 generate them is ≤ 0. Thus, during the elimination process of a pseudograph with k hanging edges, there can be 325 eliminated at most k non-composite (2, 1) vertices.

326

The composite vertices can be grouped in order to fit Definition 4 and subsequently the worst case scenario 327 for their elimination follows Lemma 11 bounding the average cost from the quantity indicated in Lemma 12. The 328 dichotomy described and the grouping are essential, because if single vertex elimination was considered for all (2, 1) 329 vertices, then the bound would be higher. This is the delicate part of our analysis.

330

The following lemma shows that we need to consider only composite vertices (2, 1) in J for our elimination 331 process.

332

Lemma 14. There is always an elimination process such that all composite non-cut vertices with normal degree 2 333 are created after the elimination of a vertex of a sub-pseudograph J in FJ .

334

Proof. The only way to create a vertex with normal degree 2 is by eliminating the neighbour of a vertex with normal 335 degree 3. By Definition 4, if the eliminated vertex has also degree 3, or is a composite vertex, then it belongs to FJ , 336 so our case holds.

337

If at a certain instance of the elimination there are no vertices with normal degree 3 there is nothing to prove.

338

If the vertices with normal degree 3 are all cut vertices, then we can continue the elimination process eliminating a 339 vertex that lies in the leaf of the block cut tree containing this cut vertex. By Lemma 7 there is always a non-cut 340 vertex u in this biconnected component, with normal degree smaller than 3. If the cut vertex v has normal degree 3 341 and u has normal degree 1, then after its elimination v is a non-composite vertex. If u has normal degree 2, then v 342 remains a cut vertex and cannot be eliminated before a further drop of degree in one of the next elimination steps.

343

It is clear from Definition 4, that all vertices of J but the leading vertex v0 are eliminated with normal degree 344 2, since when one vertex is eliminated, then the normal degree for all its neighbours drops by 1 in the resulting 345 pseudograph. The following corollary shows how we can bound the average cost of such paths in the case of Laman 346 graphs.

347

Lemma 15. The eliminating average cost for the elimination of composite vertices can be set as less or equal to 5/3.

348

This is a specialization of Lemma 12 for d = 2.

349

Proof. We show that the worst case scenario for the total and the average cost is covered by Equation 6that results from the recursive Equations 4 (see Lemma 9 for details). Let C(ℓ) denote the cost of elimination for the first ℓ + 1 vertices of a sub-pseudograph J ∈ FJ . Let also B(ℓ) denote the number of pseudographs with a (2, 1) vertex to be eliminated and G(ℓ) the number of pseudographs with a (2, 0) or (2, 2) vertex (which is a trivial vertex) to be eliminated, when l ≥ 1. Then, we have that C(ℓ) = 2B(ℓ) + G(ℓ), since the cost of a trivial vertex is 1, while the cost for a non-trivial one is 2. This definition for C(ℓ) is a specialization of Equation 5 in the case of d = 2, if we substitute C2 with C, B2 with B and G 2 with G. Lemma 9 gives the scenarios for the distribution of the hanging edge. Thus, the elimination of a (2, 1) vertex results to two different scenarios, indicating that the neighbour in the path becomes a (2, 1) vertex in half of the cases, and a trivial one in the other cases (see Figures 5,6). On the other hand for the neighbour of a trivial vertex there is only one scenario, it will be either (2, 1) (Figure 5) or again trivial (Figure 6). Let us denote by G * (ℓ) the number of pseudographs with trivial vertices that create (2, 1) vertices and G ′ (l) the number of pseudographs with trivial vertices that create other trivial vertices. This implies that G(ℓ) = G * (ℓ) + G ′ (ℓ). So, for the next vertex in J (if such exists) we derive the following equations:

B(ℓ + 1) = B(ℓ) + G * (ℓ) G(ℓ + 1) = B(ℓ) + G ′ (ℓ)
leading to the following relation for the total cost of a path after the elimination of the next vertex:

C(ℓ + 1) = 2B(ℓ + 1) + G(ℓ + 1) = 2B(ℓ) + 2G * (ℓ) + B(ℓ) + G ′ (ℓ) = 2B(ℓ) + (G * (ℓ) + G ′ (ℓ)) + B(ℓ) + G * (ℓ) ≤ C(ℓ) + B(ℓ) + G(ℓ) = C(ℓ) + 2B(ℓ -1) + G * (ℓ -1) + G ′ (ℓ -1) = C(ℓ) + C(ℓ -1) (10)
The last quantity proves that the cost function for J follows, in the worst case, function C2 in Lemma 11 3 .

350

We need to specify the different initial conditions of the path in order to prove that the total cost of the path 351 permits to use D(2) = 5/3 as an upper bound for the eliminating average cost. By Lemma 14, we consider only the 352 elimination for paths of vertices in J , so the initial vertices can have only normal degree 3. If v0 is a (3, 0) or a (3, 1)

353 vertex and has cost 3, then the sequence C(ℓ) in the worst case scenario is exactly the one of Lemma 11 for d = 2.

354

If v0 is a (3, 2) vertex and v1 is eliminated as a (2, 1) vertex, then the ratio C(1)/C(0) = 2 > 5/3. We overcome 355 this situation by making use of the eliminating average cost setting that C * (0) = 3, while C(1) is not altered. This 356 change cannot surpass the number of orientations in our analysis, since the total cost of the path is not altered.

357

Furthermore, for single vertex elimination in the case of r = 3 we have already considered a bound for the cost of 358 vertices with such normal degree, as mentioned before, which is 3. Since C( 1) is smaller than the respective value of 359 the sequence in Lemma 11, the next terms will be also smaller, so the eliminating average cost for all vertices but 360 the leading one is bounded by 5/3.

361

Now we are ready to bound from above the number of valid 2-orientations.

362

Theorem 16. The total number of 2-orientations for a connected 2-pseudograph with n vertices and k hanging edges derived by will be at most

3 (n+1)/2 • (2/3) k .
Proof. We consider that throughout the elimination process there have been eliminated t vertices with normal degree 363 3, m non-composite (2, 1) vertices, ℓ vertices with normal degree 2 in paths J , s2 trivial non-composite vertices and s1 vertices with normal degree 1. Recall that the elimination process stops when the tree condition is satisfied.

v 0 v 1 v 2 cost = 3 2 v 1 v 2 cost = 5 v 2 cost = 8 v 1 v 2 v 2 v 2

365

Neglecting trivial vertices, the total cost is bounded by

366 3 t • 2 m • (5/3) ℓ (11)
Now we will use the tree condition in order to find a bound up to n and k. If the final number of vertices and hanging edges in the elimination process are n ′ and k ′ respectively then we have the following equations:

n ′ = n -t -m -ℓ -s1 -s2 k ′ = k + t -s1 Since n ′ + 1 = k ′ , we conclude that t ≤ n -k -m -ℓ + 1 2 .
This results to

3 t • 2 m • (5/3) ℓ ≤ 3 n/2 • 3 -k/2 • 3 -m/2 • 3 -ℓ/2 • 3 1/2 • 2 m • 5 3 ℓ = 3 n/2 • 2 3 k • 5 3 3/2 ℓ • 3 1/2 ≤ 3 n/2 • 2 3 k • 3 1/2
since m is at most k (as a consequence of Definition 13).

367 Thus, the asymptotic order for the number of valid orientations for a connected 2-pseudograph up to the number 368 of its vertices n is O 3 n/2 . Subsequently we have that given a pseudograph J derived from a Laman graph with g

369 v 0 v 1 v 2 cost = 3 2 v 1 v 2 v 2 v 2 v 1 v 2 cost = 4 v 2 cost = 5
Figure 6: Another example of a J ∈ F J that induces a path in J. The example is similar to Figure 5, with the difference that v 1 is a (3, 0) vertex, and the total cost is lower. In this case, the removal of v 0 results to 2 trivial and one non-trivial case for v 1 .

connected components, then its number of valid 2-orientations is bounded by:

370 3 (n+g)/2 • 2 3 k . (12)
Nevertheless, we prove that an exact bound on the embedding number of Laman graphs can be derived considering

377

If one of the two components, i.e. G1, does not contain a separator, then S1 is called extreme. This means that 378 either G[V (G1)] contains edges, but the deletion of any 2 vertices does not break the connectivity, or there are no 379 edges in G[V (G1)]. In the latter case, every edge that is incident to a vertex in G1, has its other endpoint in S1.

380

If S1 is not an extreme separator, we repeat the process in G1 without loss of generality, setting a new partition in 381 G2, S2, G ′ 2 as before. We end the process when a separator in one of the two components is extreme.

382

Let us denote the two components and the separator in the end of this process with GS, G ′ S and S respectively.

383

We consider GS to be the component with no separator. If there is an edge in one of the components, then trivially 384 the deletion of its endpoints does not break the connectivity.

385

If there is no edge in GS, then let u, u ′ be the vertices in S and v be a vertex in GS. Since G is 2-connected, then 386 v has degree at less 2, so there are edges (u, v) and (u ′ , v). Since there are no edges in GS and both u and u ′ connect 387 with both GS and G ′ S , the removal of v and one of these 2 cannot break the connectivity.

388

Theorem 18. Let G = (V, E) be Laman: the embedding number of G in C 2 and S 2 is bounded from above by

16 3 7/2 • 2 • 3 1/2 |V |-2 .
The asymptotic order of this bound is O(3.46 |V | ).

389

Proof. In [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings 605 of minimally rigid graphs[END_REF] it is proven that the bound of the embedding number for a Laman graph G with a 2-valent vertex v 390 is the same with the number of orientations of the graph G \ {v}, so by Theorem 1 the number of orientations is 391 the same. This means that for the general bound, we may consider only Laman graphs with minimum degree 3.

392

Since the number of hanging edges k is equal to the number edges incident to the fixed vertices, but for the fixed 393 vertex, we have that k ≥ 4. Also, Lemma 17 indicates that there is always a fixed edge whose removal does not break 394 connectivity.

395

By setting k = 4 and g = 1 in the upper bound on the 2-orientations given in Equation 16, and combining it with 396 Theorem 1 we derive the new upper bound. In this section we improve the bounds for all d ≥ 3. The elimination method here is analogous with d = 2. The 399 main difference is that paths with multiple normal degree profiles shall be considered. Remark also that the case of 400 Laman graphs is used as base case for some of our proofs. The asymptotic bound derived in this section is given by 401 the following Theorem, that extends Theorem 18.

402

Theorem 19. Let G = (V, E) be a minimally rigid graph in dimension d ≥ 2. The embedding number of G is bounded from above by

O      2 • 2d -1 d 1/2   |V |    .
Recall that C d (r, h) denotes the cost of the removal of a vertex with r normal edges and h hanging edges for

is the asymptotic effect for the elimination of a vertex with degree profile (r, h), r ≥ 2. The exponent in this quantity 405 is not affected by the hanging degree of the vertices, so it is the same for all vertices with the same normal degree.

406

We also consider that the asymptotic effect of vertices with normal degree 1 is trivially 1. Let us recall that there is 407 no need to examine vertices such that r + h < d or h > d, since they have no valid d-orientations [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF].

408

The first step leading to the bound of d-orientations is to derive the maximal of the asymptotic effect for certain 409 cases of degree profiles. More precisely we prove that the asymptotic effect of (2d -1, 0) vertices is bigger or equal 410 to the asymptotic effect of all other vertices examined in the following lemma. Thus, C d (2d -1, 0)

414

Proof. The case of r = 1 is trivial by definition.

415

For the non-trivial cases, we first prove initially that C d (r, 0)

d-1
r-1 is monotonically increasing for all integers in r ∈ [d, 2d -1]. This corresponds to the asymptotic effect of vertices with no hanging edges. We are interested only in this interval since by Lemma 7 there is an elimination process such that the maximum normal degree is 2d -1 and r + h ≥ d. Observe that the term d -1 is constant, so it suffices to prove that the ratio

U d (r) = C d (r + 1, 0) r-1 C d (r, 0) r = r+1 d r d r-1 • 1 r d = r + 1 r + 1 -d r-1 • 1 r d
is bigger than 1 in this interval.

416

If we take the ratio

U d (r + 1) U d (r)
we conclude that

U d (r + 1) U d (r) = (r + 2)(r + 1 -d) (r + 1)(r + 2 -d) r = 1 - d (r + 1)(r + 2 -d) r is always smaller than 1 ∀d ≥ 2, so U d (r) decreases and its minimum in [d, 2d -1] is U * (d) = U d (2d -1) = 2 2d-2 2d-1 d
.

For d = 2 we have U * (d) = 4/3 > 1 and it can be checked that

U * (d + 1) U * (d) = 1 + 1 2d + 1
, proving that ∀d ≥ 2:

U d (2d -1) > 1.
This implies that, we have that C d (r + 1, 0) 1/r > C d (r, 0) 1/(r-1) for every r ∈ [d, 2d -1], concluding our claim.

417

The cases for 1 ≤ h ≤ d and dh ≤ r ≤ 2 • (dh) -1 can be related with the bounds on the orientations in lower dimensions. Thus, we prove by induction that if the maximum for the asymptotic effect holds for dh it also holds for these cases for d. We just proved that

C d-h (r, 0) (d-h-1)/(r-1) ≤ C d-h (2(d -h) -1, 0) 1/2
holds in dimension dh, with dh ≥ 2 (the base case for dimension 2 was proven in Section 3).

418

So we need to prove the last part of the following inequality

419 C d-h (r, 0) (d-1)/(r-1) ≤ C d-h (2(d -h) -1, 0) (d-1)/(2(d-h)-2) = C d (2(d -h) -1, h) (d-1)/(2(d-h)-2) ≤ C d (2d -1, 0) 1/2 .
(14) This will be done by demonstrating that the ratio

C d (2(d -h) -1, h) 2(d-h-1)-2 C d (2(d -h -1) -1, h + 1) 2(d-h)-2
is always bigger than 1 for 0 ≤ h ≤ d. In other words, the shift h → h + 1 reduces the asymptotic effect. Considering d * = dh, this shift turns to d * → d * -1 and the ratio becomes

W (d * ) = C d * (2d * -1, 0) 2d * -4 C d * (2d * -3, 1) 2d * -2 = 4d * -2 d * 2d * -4 1 2d * -3 d * -1 2
which is bigger than 1 for d * = 3, since 10 2 > 3 4 .

420

Now the ratio

W (d * ) W (d * -1) = (4d * -2)(d * -1) (4d * -6)d * 2d * -6 •       2d * -5 d * -2 2d * -3 d * -1 • 4d * -2 d *       2 = 1 + 2 4d * 2 -6d * 2d * -4
is also bigger than 1, showing that W (d * ) is increasing. The same comparison with (2(dh) + 1, h -1) vertices can be done for ( 2(dh

) + 1, h * ) with h * ≥ h, since 425 C d (2(d -h) + 1, h) = C d (2(d -h) + 1, h -1
) and all vertices with more hanging edges have smaller cost. Finally, 426 we remark that in the previous 2 cases the cost function was maximized for vertices with h hanging edges, from the 427 properties of binomial coefficients. Thus, in examining the case r ≥ 2(dh) + 2, we refer to the cases of vertices with 428 fewer hanging edges that shall have higher cost. Our base case now is the (2d -1, 1) and (2d -1, 2) vertices. The 429 first have asymptotic effect equal to the target bound, while the latter have strictly smaller effect.

430

Vertices with degree profile (2(dh), h) cannot be included in this analysis for all dimensions, since the ratio

C d (2(d -h), h) 2d-2 C d (2d -1, 0) 2(d-h)-1
is strictly larger than 1. Notice that this case is treated in dimension 2 for (2, 1) vertices. Moreover, this condition is 431 inherited for vertices with the same normal degree and increased hanging degree in bigger dimensions. For instance, 432 the cost C d ′ , would be to consider

B d ′ (1) = α d 2 (B d ′ (0) + G d ′ (0)) and G d ′ (1) = α d 2 B d ′ (0) + (β d -α d 2 )G d ′ (0).

486

Now we prove that 487

C d ′ (1) C d ′ (0) ≤ α 2 d ′ + β 2 d ′ α d ′ + β d ′ (15)
for all the cases in which the total cost of J d follows the worst case scenario.

We have that

C d ′ (1) C d ′ (0) = α d ′ B d ′ (1) + β d ′ G d ′ (1) α d B d ′ (0) + β d G d ′ (0) = α d ′ (α d • B d ′ (0)/2 + α d • G d ′ (0)/2) + β d ′ (α d • B d ′ (0)/2 + β d G d ′ (0) -α d • G d ′ (0)/2) α d B d ′ (0) + β d G d ′ (0) = α d ′ (C d ′ (0)/2 -β d • G d ′ (0)/2 + α d • G d ′ (0)/2) + β d ′ (C d ′ (0)/2 -α d • G d ′ (0)/2 + β d • G d ′ (0)/2) α d B d ′ (0) + β d G d ′ (0) = α d ′ + β d ′ 2 + (α d ′ -β d ′ ) • (α d -β d ) G d ′ (0) 2(α d B d ′ (0) + β d G d ′ (0)) Since α 2 d ′ + β 2 d ′ α d ′ + β d ′ - α d ′ + β d ′ 2 = (α d ′ -β d ′ ) 2 2 • (α d ′ + β d ′ )
and

α d ′ > β d ′ , Inequality 15 is satisfied if (α d -β d ) • G d ′ (0) α d B d ′ (0) + β d G d ′ (0) ≤ α d ′ -β d ′ α d ′ + β d ′ .
The relation (d -1) • α d = d • β d , holds for every d ≥ 2, so the inequality becomes

G d ′ (0) d • B d ′ (0) + (d -1) • G d ′ (0) ≤ 1 2d ′ -1 ⇔ (2d ′ -d) • G d ′ (0) ≤ d • B d ′ (0). Since 2d ′ -d < d and G d ′ (0) ≤ B d ′ (0)
2β d ′ ) • C d ′ (ℓ -3) ≤ 491 α d ′ (α d ′ -β d ′ ) • C d ′ (ℓ -
d ′ (1)/C d ′ (0) = (α 2 d ′ + β 2 d ′ )/(α d ′ + β d ′ ).
495 496 Lemma 23. The asymptotic effect for the eliminating average cost of paths J d-h+1 is always smaller than the 497 asymptotic effect of (2d -1, 0) vertices in the case of d-orientations.

498

Proof. The asymptotic effect in the case of paths is D(dh + 1)

d-1 2(d-h)-1 .
First we prove that this holds for h = 1.

499 Recall that α d /β d = d/(d -1). 500 D(d) 2d-2 C d (2d -1, 0) 2d-3 < 1 ⇐⇒ (α 2 d + β 2 d ) 2d-2 (α d + β d ) 4d-5 < 1 ⇐⇒ α 2 d + β 2 d (α d + β d ) 2 2d-2 • (α d + β d ) < 1 ⇐⇒ 1 - 2α d β d (α d + β d ) 2 2d-2 • (α d + β d ) < 1 ⇐⇒ 1 - 2d • (d -1) (2d -1) 2 2d-2 • 2d -1 d < 1 ⇐⇒ 2d 2 -2d + 1 (2d -1) 2 2d-2 • 2d -1 d < 1
which holds for d = 2. So we need to show that the following function is monotonically decreasing for d ≥ 2.

501

A(d) = 2d 2 -2d + 1 (2d -1) 2 2d-2 • 2d -1 d
We have that

A(d + 1) A(d) = 2(d + 1) 2 -2(d + 1) + 1 (2d + 1) 2 2d • 2d + 1 d + 1 2d 2 -2d + 1 (2d -1) 2 2d-2 • 2d -1 d = 2(d + 1) 2 -2(d + 1) + 1 (2d + 1) 2 2d • 2(2d + 1) 2d 2 -2d + 1 (2d -1) 2 2d-2 • (d + 1) = (2d -1) 2 • (2(d + 1) 2 -2(d + 1) + 1) (2d + 1) 2 • (2d 2 -2d + 1) 2d-2 • 2 • (2(d + 1) 2 -2(d + 1) + 1) 2 (2d + 1) 3 • (d + 1) = 8d 4 -2d 2 -2d + 1 8d 4 -2d 2 + 2d + 1 2d-2 • 8d 4 + 16d 3 + 16d 2 + 8d + 2 8d 4 + 20d 3 + 18d 2 + 7d + 1 .
Both fractions are less than 1 for all d ≥ 1.

502

Now, since this inequality holds in dimension d, we use the fact that in smaller dimensions 503

D(d -h + 1) d-h-1 2(d-h)+1 ≤ C d-h+1 (2(d -h + 1) -1, 0) 1/2 (16)
for h ≥ 2. This means that D(dh + 1)

d-1

2(d-h)+1 is bounded using similar inequalities as in Equation 14from 504 Lemma 20.

505

Finally, we prove that the asymptotic effect of non-composite (2(dh), h) vertices is maximized for h = d -1.

506

Lemma 24. The following ratio is bigger than

1 for 1 ≤ h ≤ d -2. 2 2(d-h)-1 C d (2(d -h), h)
(n+ 1 d-1 )/2 •        2 2d -1 d 1 d-1        k (17)
Proof. Let us list the basic categories of vertices to be eliminated and provide a notation for their cardinalities during 511 the elimination process.

512

• t d vertices with normal degree 2d -1. For these vertices we consider the maximum cost C d (2d -1, 0).

513

• sr vertices with degree profile (r, h), such that their asymptotic effect is strictly smaller than the target bound.

514

For these vertices, we consider the effective cost of their elimination omitting h from the cost function:

C * d (r) = 515 max 0≤h≤d h =(r-2d)/2 C d (r, h).

516

Remark that the condition h = (r -2d)/2 applies only in the case of vertices with even normal degree.

517

• ℓ h vertices with normal degree 2(dh), for 1 ≤ h ≤ d -1 eliminated with path elimination step.

518

• m h vertices with degree profile (2(dh), h), such that their asymptotic effect is bigger than the target bound.

519

Selecting the maximum cost for the first two cases allows us to use the eliminating average cost for path bounds.

520

The total cost of the elimination process is bounded by

521 C d (2d -1, 0) t d • C * d (r) sr • D(d -h + 1) ℓ h • C d (2(d -h), h) m h (18)
By Lemma 5, the elimination process stops when tree condition (d -1) • n ′ + 1 = k ′ is achieved, where n ′ and k ′ denote the number of vertices and hanging edges at this instance. This means that

n ′ = n -t d -sr -ℓ h -m h k ′ = k + (d -1) • t d + (r -d) • sr -(d -2h) • ℓ h -(r -d) • m h
were k ′ is derived by applying the H.E.E. formula (see Lemma 8). These equations combined with tree condition lead to the following inequality on t d :

t d ≤ n 2 - 1 + k -(r -1) • sr -(2(d -h) -1) • ℓ h -(r -1) • m h 2d -2
Applying this inequality to Equation 18, it is deduced that the following quantity bounds the number of orientations ). First we prove that 2 d-1 C(2d -1, 0) < 1, thus the number of hanging edges k does not increase the bound (see Equation 17). Observe that the ratio [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings 605 of minimally rigid graphs[END_REF] using matrix permanents, BEV is the bound derived in [START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF] using elimination to bound outdegree-constrained orientations, and new is derived in this paper.

C d (2d -1, 0) n 2 -k-1 2d-2 • C * d (r) C(2d -1, 0)
2 d • 2d-1 d 2 d-
5 Lower bounds on the maximal number of mBe.

532

In the previous sections, we improve the upper bound for the embedding number of minimally rigid graphs. Despite the subject of a whole publication [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]), we are also interested in the tightness of our results with respect to the mBe using repetitive Henneberg steps [START_REF] Schulze | Rigidity and scene analysis[END_REF] to Laman graphs with big embedding number (data for the embedding numbers 546 was found in [START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]). To provide these bounds, we calculate them using the code from [START_REF] Bartzos | Source code and examples for the paper "On the multihomogeneous Bézout bound on 613 the number of embeddings of minimally rigid graphs[END_REF].

547

Given a Laman graph G(V, E), we denote with µ(G) the number of its complex embeddings. Recall that mBe(G, e)

29

  respectively the set of vertices and edges of G, while G[V ′ ] denotes the subgraph of G induced by a subset of30 vertices V ′ ⊆ V (G). An embedding of G in R d is an assignment of the vertices of G, to a configuration in R d , 31 p = {p1, . . . , p |V | } ∈ R d•|V | .A graph G and a configuration p constitute a framework G(p) in R d . In the case of 32

110 called pseudograph. 111 Definition 2 .

 1112 A pseudograph J is a triplet (VJ , EJ , HJ ), such that VJ denotes the set of vertices, EJ denotes the 112 set of normal edges incident to two vertices, and HJ denotes a set of edges, called hanging edges, that are incident to 113 only one vertex in VJ . The hanging edges are directed outwards.

  114

0 Figure 2 :

 02 Figure 2: An example sub-pseudograph J 2 of a graph J that satisfies Definition 4. Although all vertices have normal degree 3 in this example, they are all eliminated with normal degree 2 except for v 0 .

169

  Then (i) the number of valid orientations of J is either 1 or 0, and (ii) if G has a valid orientation, then |HJ | = 170 (d -1) • |VJ | + 1, where d is the fixed outdegree required. 171 This count is derived from the relation |EJ | = |VJ | + 1 between the edges and the vertices of a tree and the count 172 of Lemma 3. Notice that if we allowed the elimination of cut vertices, then the edge count for g connected trees would 173 be |EJ | = |VJ | + g, so the relation between the hanging edges and the vertices would become |HJ | = (d -1) • |VJ | + g.

Figure 3 :

 3 Figure 3: (left) An example graph. B 1 , B 2 , B 3 and B 4 are the biconnected components. (right) The block-cut tree of the example graph.

  244

Figure 4 : 3 2 = 3 .

 433 Figure 4: The cost of the elimination of a vertex is equal to the number of different valid ways of adding direction on its edges. (left) Elimination of a (3, 0) vertex in the case of d = 2. The cost in this case is 3 2 = 3. Two edges shall be deleted, therefore only one of its neighbours acquires a hanging edges. (right) Elimination of a (3, 2) vertex in the case of d = 3.The two hanging edges of this vertex shall be removed and the same shall happen for one of its normal edges. The remaining two edges will become hanging edges on their other endpoint. Therefore the cost is3 3-2 = 3 and every neighbour acquires a hanging edge in 2 scenarios.

Definition 10 .

 10 258 profile (r, h) and the non-leading vertices J d -{v0}. For the first one, we consider the cost C d (r, h) as in the case of 259 single vertex elimination step. In order to compute C d (ℓ), we use the formula of Lemma 8 taking into account every 260 possible scenario for the degree profile of the non-leading vertices. If it is required, we may use an upper bound for 261 the cost of v0, which is the effective cost and equals to C * d (r) = max 0≤h≤d C d (r, h). For the other vertices, we need to 262 introduce the following definition, which is a variant of the definition of the cost for single vertices. 263 Let J d = (v0, v1, . . . , v ℓ ) be a path of ℓ + 1 vertices, as in Definition 4, with ℓ ≥ 1. Let C d (ℓ) be the total cost of removing these vertices in order. The average cost of removing the path without the first vertex v0 is

274

  why we define here C d , B d and G d is to show that the total cost of our paths (in the worst case scenario) follows the 275 pattern of the recursive sequences given in these lemmas. This is done in Sections 3 and 4. First, we define B d and 276 G d recursively. Then, we define C d using these functions and prove a new recursive formula on C d . 277 Lemma 11. Let B d (ℓ) and G d (ℓ) be the following recursive functions:

280Lemma 12 .

 12 In the sequel we set B d (0) = G d (0) = 1 as initial condition for these sequences. Notice that by the definition of 281 the sequences in equation 4, we have thatB d (ℓ) > G d (ℓ), since α d > β d , for all ℓ ≥ 1.282 Now we are ready to bound the ratio of two consecutive terms of the sequence C d (ℓ). This is used to bound the 283 cost of vertices eliminated with a path elimination step. 284 For all ℓ ≥ 0 and d ≥ 2 the ratio C d (ℓ + 1) C d (ℓ) is strictly bounded from above by 285

289

  For C d (1)/C d (0), we simply use the definition C d (ℓ + 1) = α d B(ℓ + 1) + β d G(ℓ + 1), for ℓ = 0 and we find the values of B(1) and G(1) by using their definition. Recall that B(0) = G(0) = 1. Hence, we have the following equality:

301(Lemma 5 )

 5 signifies the termination of the process. Given a pseudograph J = (VJ , EJ , HJ ) and setting n = |VJ | and 302 k = |HJ |, we have that this condition is satisfied if k = n + 1.

305 2 -•••

 2 pseudographs derived from the deletion of a fixed edge in a Laman graph always contain a non-cut vertex with 306 normal degree less or equal to 3. This also happens for all connected pseudographs that evolve through the elimination 307 process, signifying that those that have valid 2-orientations may have vertices with the following vertex profiles, cost 308 and H.E.E. (see Equation1):309 Vertices with normal degree 1 have H.E.E. = -1: (1, 2), (1, 1), with cost=1.310 Vertices with normal degree 2 have H.E.E.= 0: (2, 2), (2, 0), with cost = 1, and (2, 1), with cost = 2.311 Vertices with normal degree 3 have H.E.E.= 1: (3, 2), with cost = 1, and (3, 0),[START_REF] Bartzos | On the maximal number of real embeddings of minimally 603 rigid graphs in R 2 , R 3 and S 2[END_REF][START_REF] Asimow | The rigidity of graphs[END_REF], with cost = 3.

Figure 5 :

 5 Figure 5: An example of a path elimination (left to right). Weights on blue arrows show that a pseudograph is produced many times. Above each step, there is the cost of the corresponding elimination. (left) The first vertex v 0 has degree profile (3, 0) and is eliminated with a single vertex elimination step. (middle) There are 3 different scenarios for the distribution of hanging edges after eliminating v 0 . In 2 of them v 1 becomes a (2, 1) vertex, while in the other case it becomes a (2, 2) vertex. The total cost for the removal of v 1 adding all cases is 2 • 2 + 1 = 5. (right) The elimination of v 2 follows the same principle. The average cost for the elimination of v 1 and v 2 is (8/3) 1/2 < 5/3. If we did not apply the path elimination step, we should have eliminated vertices v 1 , v 2 with cost 2 (which is the highest) and the total cost would be 3 • 2 • 2 = 12.

371aLemma 17 .

 17 fixed edge, whose removal does not create multiple components. Recall from graph theory that given a connected 372 graph G = (V, E), a subset of vertices S ⊆ V is called vertex separator if its removal breaks the connectivity.373 Let G be a Laman graph, then ∃e = (u, v) ∈ E(G) such that G ′ = (G \ {u}) \ {v} is connected.374Proof. Since G is a Laman graph, it is at least 2-connected[START_REF] Schulze | Rigidity and scene analysis[END_REF]. If the minimum size separator contains at least 3 375 vertices, then the lemma is proven. In the other case, we denote a 2-vertex separator with S1. If we remove S1 from 376 G, then we get two components G1, G ′ 1 .

  403 d-pseudographs (Lemma 8). The following quantity 404 C d (

1 2 shall be called 411 target bound in the sequel. 412 Lemma 20 .

 141141220 The asymptotic effect is maximized over all 1 ≤ r ≤ 2d -1 with 0 ≤ h ≤ d for (r, h) = (2d -1, 0), but 413 for the cases (r, h) = (2(dh), h) with 1 ≤ h ≤ d -1.

421

  What remains is to deal with the case of (2(dh), h * ) vertices with h * ≥ h + 1, as well as the case of vertices with r ≥ 2(dh) + 1 and more or equal than h hanging edges. Notice that in the first case if the term 2(dh) in 2(dh) dh * , if fixed, then this binomial coefficient decreases as h * ≥ h increases. Since we have that C d (2(dh), h + 1) = 422 C d (2(dh), h -1)and vertices (2(dh), h -1) have smaller asymptotic effect than (2(dh) + 1, h -1) vertices as 423 proven before, our hypothesis is valid.

  424

2 d ′ +β 2 d

 22 the inequality is proven. 488 It remains to show C d ′ (ℓ + 1)/C d ′ (ℓ) ≤ α ′ α d ′ +β d ′ , for ℓ ≥ 1. The sequence follows at the worst case the recursion 489 established in Lemma 11, so we may use the inequalities established in the proof of Lemma 12 to prove the cases 490 of C d ′ (ℓ + 1)/C d ′ (ℓ) with ℓ ≥ 1. For ℓ ≥ 4 there is nothing to prove since the inequality (α d ′ -

Proof. 1 ,

 1 Let us denote d * = d-h as in Lemma 20 and by S(d * ) the above ratio. Since the shift d * → d * +1 corresponds to the shift h → h -1. Taking the ratio S(d * + 1) one deduces that S(d * ) is clearly increasing. Since S(2) = 8/6, the condition holds. 507 Now we are ready to prove the bound on d-orientations. 508 Theorem 25. The number of d-orientations for a connected d-pseudograph with n vertices and k hanging edges is

.

  Since the terms the asymptotic effect of vertices (2d -1, 0) is bigger than the asymptotic effect of vertices in the first product and paths in the second product (seeLemmata 20 and 21) and the asymptotic effect of non composite (2, d -1) vertices is the biggest among the cases of vertices with asymptotic effect exceeding the target bound (see Lemma 24), we deduce that the orientations are bounded by By the definition of non-composite vertices with asymptotic effect bigger than the target bound, we have thatmh 522 is bounded by the initial number of hanging edges k. Thus, the bound in Equation 17 follows. 523 Lemma 26. Let G be a minimally rigid graph in dimension d. There is a fixed subgraph K d ′ in G, with d ′ < d, that 524 its removal does not break the connectivity of G. 525 Proof. The graph G is at least d-connected. Let S be the minimum separator of G. Note that |S| ≥ d. Hence the 526 removal of any subgraph of G with less than d vertices cannot break its connectivity. 527 Now we are ready to prove Theorem 19. 528 Proof (Theorem 19

533

  this improvement, still the gap between the new upper bounds and lower bounds in the bibliography remain: in the 534 case of Laman graph embeddings in C 2 the asymptotic order of the new upper bound is O 3.4641 |V | , while there 535 have been reported graphs with at most Ω 2.3780 |V | complex embeddings. Besides computing graphs with big 536 number of embeddings and establishing new lower bounds (which requires big computational resources and has been 537

538

  and the number of outdegree-constrained orientations. Recall, that the bounds of Theorem 18 and Theorem 19, are 539 actually bounds on the m-Bézout bound of algebraic systems (as explained in[START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings 605 of minimally rigid graphs[END_REF]) and use bounds on orientations 540 that we establish in Theorem 16 and Theorem 25. 541 Thus, in this section we provide examples of Laman graphs with maximal number of 2-orientations, among certain 542 cases we computed, and we compare them with the bound on the embeddings given in Theorem 18 and the bound 543 on the orientations given in Theorem 16. Let us remark that an exhaustive search over all Laman graphs with big 544 number of vertices is almost infeasible, since their number is gigantic. For that reason, graphs were constructed by 545

548 7 / 2 • 2 • 3 1 / 2

 72212 denotes the bound derived from Theorem 1 for a fixed edge e = (u, v) ∈ E and R(G, e) the corresponding number of 549 orientations. 550 Then applying Theorem 18, the following inequality holds: 551 µ(G) ≤ min e∈E (mBe(G, e)) ≤ mBe(G, e) ≤ 16 3 |V |-2 (19) since the bound can vary for different fixed edges. In the case of Theorem 16 we have the following inequality: 552 R(G, e) ≤ 3 n/2 • (2/3) k • 3 1/2 ,

  Additionally, we impose certain restrictions on the normal degree of the removed vertex. For that 178 reason, let us recall the definition of the block-cut tree. This definition is necessary to prove the existence of non-cut

	179
	vertices with bounded normal degree.

177 d-pseudographs. 180 Definition 6 ([14]). Let G = (V, E) be a connected graph. There is a graph BG, such that every vertex of BG 181 represents either a biconnected component in G, or a cut-vertex in G and its edges represent a biconnected component 182 and a cut-vertex that belongs to that biconnected component. This graph is called the block-cut tree of G.

  Consider a leaf of the block-cut tree BJ * . We denote In order to exploit the elimination process to bound the number of d-orientations, we need to define two quantities 202 for every elimination step. These are first defined in the case of the single vertex elimination step and specialized 203 for path elimination steps. Let J be a pseudograph in which vertex v is eliminated. Then the number of ways to

	204
	205	choose the normal edges that remain in the resulting pseudograph as hanging edges corresponds to different resulting
	206	pseudographs that may have valid d-orientations. This number is the cost of the elimination step. Notice that the
	207	only requirements for the elimination process are the connectivity and the edge count of Lemma 3. Since the latter
	208	is a necessary condition (and not always sufficient) for the existence of a valid d-orientation, this means that some
	209	of the choices may result to pseudographs with no orientations. This means that the cost in each elimination step
	210	bounds the number of valid orientations for the edges incident to the the vertex that is to be eliminated in this
	211	particular step. This bound depends on the degree profile of this vertex, as well as the combinatorial properties of
	212	the pseudograph. Let us remark, that the cost of multiple steps has multiplicative effect: if eliminating the vertex v1
	213	from J has cost c1 and in the next step v2 is eliminated with cost c2, then the total number of orientations for these
	214	two steps is bounded by c1 • c2. In other words, the cost of the removal of a vertex v expresses the quotient of the
	215	number of valid orientations of J over the maximum number of valid orientations of the resulting pseudographs. This
	216	property will be used in the case of path elimination to refine our analysis. Let us comment here the main difference
	217	in our analysis between path elimination step and single vertex elimination step: when eliminating two consecutive
	218	vertices v1 and v2 in the first case we consider for v2 the cost from all resulting pseudographs, while in the second
	219	case we consider for v2 only the resulting pseudograph in which the cost of v2 is maximized. Finally, we remark that
	220	the total cost of the elimination process bounds the number of orientations.
	221	A second quantity we use is the hanging edges equilibrium, which is the difference between hanging edges in
	222	the resulting pseudographs and in J. This gives a hint about how fast the elimination process may approach the
	223	tree condition: for each vertex elimination the number of vertices in the resulting pseudograph drops by 1, but the
	224	number of the total hanging edges varies depending on the vertex profile of the eliminated vertex (see Lemma 5 for
		the equation relating vertices and hanging edges if the normal subgraph is a tree).
	190
	191	the vertices of the biconnected component that corresponds to a leaf of BJ * by L. The sum of normal degrees for all
	192 193	vertices in J * [L] is at most 2d • |V (J * [L])| -2 d+1 2 . In it, there is at most one vertex which is a cut-vertex of J * , because BJ * is a biconnected component. The cut vertex has normal degree at least 2 in J * [L]. Assume that the
	194	smallest normal degree for a non-cut vertex in the leaf is 2d. Then, it follows that the sum of normal degrees for all
	195	vertices in J * [L] is at least 2d • |V (J * [L])| -2(d -1), violating Maxwell's condition. This leads to a contradiction,
	196	because Maxwell's condition shall be satisfied for J * [L], so there are always vertices with normal degree smaller or
	197	equal to 2d -1.
	198	Throughout the elimination process this property holds, since the normal subgraph of any pseudograph derived
	199	from an elimination step is always a subgraph of a minimally rigid graph.
	200	Notice that in [6], the bound on the valid d-orientations was related to all connected pseudographs, while this
		lemma restricts the analysis to pseudographs derived from minimally rigid graphs, i.e. d-pseudographs.

201

  The eliminating average cost is used when we want to 267 bound effectively the process by using an upper bound in the case of C d (0), instead of the exact cost. A necessary 268 condition when using the average cost is that the H.E.E. is not altered by these changes, compared with the case 269 of single vertex elimination. This happens because H.E.E. depends only on normal degree (see Equation2). The 270 eliminating average cost is used to decrease the ratio of the average cost. The cost for the path elimination is not

	271
	affected by this modification: setting C * d (0) as the cost for v0 and
	1/ℓ
	is the eliminating average cost.

264

This shall be considered the cost for each vertex in J d -{v0}. This modifications are necessary, since if vertices 265 with degree profile (2(dh), h) for 1 ≤ h ≤ d -1 were always eliminated with a single vertex elimination step, then 266 the analysis would lead to bigger bounds on d-orientations.

Table 1 :

 1 ≥ 2. This implies that 2 d-1 < C(2d -1, 0) holds for every d ≥ 2, since for d = 2 we have that 2 < 3 2 .Lemma 26 indicates that there is always at least a fixed K2 that is not a separator for d ≥ 3. The bound results 530 applying Theorem 25 for d-orientations to Theorem 1. The base to the power of |V | for the asymptotic bound in dimensions 2 ≤ d ≤ 9. Bézout denotes the Bézout bound, BES is the bound derived in

	1 • 2d+1 d+1	=	d + 1 2d + 1	< 1

529

In[START_REF] Bartzos | New upper bounds for the number of embeddings of minimally rigid 611 graphs[END_REF], the degree profile is a pair (q, h), where h is the same as here, and q equals to the sum of degrees r + h. Since the focus here is different, we make this modification in the notation.

The worst-case scenario for the cost sequence in dimension 2 has the same recursive definition as the Fibonacci sequence.

in dimension 3, the vertices with higher asymptotic effect than the target bound are both the (4, 1) vertices and the 433 [START_REF] Baglivo | Incidence and Symmetry in Design and Architecture[END_REF][START_REF] Baglivo | Incidence and Symmetry in Design and Architecture[END_REF] vertices. The latter corresponds to the (2, 1) vertices in dimension 2, since they have the same cost.

434

We will treat these cases expanding the idea of grouping composite vertices presented in Section 3. Let us define 435 the dichotomy between composite and non-composite vertices in general dimension. We recall that trivial vertices 436 are the ones that have cost equal to 1. 437 Definition 21. Let J be a pseudograph, in which we apply an elimination process to bound the number of its 438 d-orientations. The non-composite vertices with normal degree 2(dh), for 1 ≤ h ≤ d -1 are the vertices with 439 degree profile (2(dh), h), (2(dh), h + 1), (2(dh), h -1) such that 440

• they had exactly this degree in J.

441

• they have this degree profile and they were generated by the removal a trivial vertex with normal degree r ≤ d.

442

All the other vertices eliminated with this degree profile are called composite vertices with normal degree 2(dh). Proof. First, we show that the cost function follows at worst case the recursion presented in Equation 6. We will 453 first consider the case of a path J d with a leading vertex v0 that has normal degree 2d -1, which can be generalized 454 in all other cases. Let B d (ℓ) denote the number of pseudographs with a (2d -2, 1) vertex to be eliminated and G d (ℓ) 455 the number of pseudographs with a (2d -2, 0) or a (2d -2, 2) vertex or (2d -2, 2) to be eliminated, when ℓ ≥ 1.

555

We compare the asymptotic order of our bounds in the number of vertices with actual results of the mBe and 556 the orientations, that are O 3.4641 |V | and O (1.7320 n ) respectively. In order to compute the asymptotic order of 557 the bound on the embeddings, we consider the number of non-fixed vertices in the exponent as in [START_REF] Bartzos | On the maximal number of real embeddings of minimally 603 rigid graphs in R 2 , R 3 and S 2[END_REF][START_REF] Grasegger | Lower bounds on the number of realizations of rigid graphs[END_REF]. This choice 558 is made due to the underlying algebraic systems that lead to the bound in [START_REF] Bartzos | On the multihomogeneous Bézout bound on the number of embeddings 605 of minimally rigid graphs[END_REF]. We also factor out the constant term 559 16 3 7/2 to derive the asymptotic order. In the case of 2-orientations, we factor out the term that is not exponential to 560 n, i.e. 3 1/2 • (2/3) k , to derive the exponential order only in n. Notice, that this number varies up to the number of 561 hanging edges. Given a fixed edge e = (u, v), the number of hanging edges for the resulting pseudograph is exactly

564

The graph G29a is a 29-vertex graph and has the maximum asymptotic bound we have computed (see Figure 7).

565

For the edge e that maximizes this bound, we have that mBe(G29a, e) = 21, 947, 282, 882, 560, so R(G29a, e) = 566 163, 520. Now, in order to find the asymptotic order of the number for mBe we compute 3 7/2 16 • mBe(G29a, e)

1/27 = 567 3.2462. In the case of orientations, notice that both fixed vertices have degree 4, so k = 6. Then we com-

1/27 = 1.6726. Thus, here we show that there are minimally rigid graphs with 569 Ω 3.2462 |V | as m-Bézout number and 2-pseudographs with Ω (1.6726 n ) orientations. We believe that with bigger 570 computational resources, these numbers can be further increased.

571

Although this graph has a big bound for this specific edge, min e ′ ∈E (mBe(G29a, e ′ )) is much lower, namely 572 416, 611, 827, 712 with an asymptotic order of 2.8029, while for the actual number of embeddings we get only 573 µ(G29a) = 1, 624, 244, 224 4 .

574

Besides the maximal mBe, we ran also computations to find graphs with big minimum mBe (see Equation 19).

575

The graph that has the maximum minimal m-Bézout number, among the ones we computed, is G 29b (see Figure 8).

576

For the edge e ′ that minimizes the bound for the specific graph, we have that mBe(G 29b , e ′ ) = 784, 502, 620, 160, 579 4 We thank Georg Grasegger for this computation 5 Let us note that Georg Grasseger informed us that their algorithm could not compute the embedding number for this graph.

21

Figure 8: The graph G 29b is also a Laman graph on 29 vertices and the dashed blue edge corresponds to the fixed edge that yields the minimum m-Bézout. For that fixed edge k = 5.

6 Conclusions and future work 580

In this project we have managed to improve the upper bounds on the embedding number of minimally rigid graphs, 581 via bounding the number of outdegree constrained orientation for certain cases. This bound is still far from the 582 lower bounds on the maximal number of complex embeddings in the cases of dimension 2 and 3, but as we show in 583 Section 5, it seems to be close to the bound on the orientations for Laman graphs. Thus, we consider that the upper 584 bound on orientations may be sharp, but demanding computations are needed to verify this conjecture.

585

More demanding computations are also required for improving the lower bounds on the embedding number that 586 may reduce the gap between lower and upper bounds. In the case that the bound is indeed sharp on orientations, 587 but loose for the embedding number, one may consider other ways to improve upper bounds. One idea is to examine 588 if there are certain combinatorial properties for the fixed K d whose removal minimizes the number of orientations.

589

Another approach would be to consider tools from sparse algebraic geometry on determinantal varieties of Cayley-590 Menger matrices.

591

Finally, our bounds may be extended generally for all outdegree-constrained d-orientations. In that case the 592 restriction on degree is not applied for (2d -1)-valent vertices, but for (2d)-valent vertices. This result may also 593 have applications on the multihomogeneous bound of certain polynomial systems, as demonstrated in [START_REF] Bartzos | The m-Bézout bound and distance geometry[END_REF].