# An asymptotic upper bound for graph embeddings

Evangelos Bartzos, Ioannis Z. Emiris, Charalambos Tzamos

► To cite this version:

Evangelos Bartzos, Ioannis Z. Emiris, Charalambos Tzamos. An asymptotic upper bound for graph embeddings. Discrete Applied Mathematics, 2023, 327, pp.157-177. 10.1016/j.dam.2022.12.010. hal-04294304

HAL Id: hal-04294304

https://hal.science/hal-04294304v1

Submitted on 28 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# An Asymptotic Upper Bound For Graph Embeddings

Evangelos Bartzos¹,², Ioannis Z. Emiris²,¹, and Charalambos Tzamos¹

¹Department of Informatics & Telecommunications, National & Kapodistrian University of Athens, Athens 15784 Greece, {vbartzos,emiris,ctzamos}@di.uoa.gr

²"Athena" Research Center, Maroussi 15125 Greece, emiris@athenarc.gr

## Abstract

We address a central question in rigidity theory, namely to bound the number of Euclidean or spherical embeddings of minimally rigid graphs. Since these embeddings correspond to the real roots of certain algebraic systems, the same enumerative question can be asked in complex spaces. Bézout's bound on the quadratic equations that capture the edge lengths yields trivially a bound of $O(2^{d|V|})$ embeddings, for graphs of $|V|$ vertices in $d$ dimensions; it had not been improved until recently. A first improvement was obtained for $d \ge 5$ [4]. The same work related the number of embeddings and the number of a class of graph orientations. A combinatorial analysis based on the latter yielded the first nontrivial upper bounds for $2 \le d \le 4$, while further improving the bounds for $d \ge 5$ [6].

Here, we follow a similar procedure as in [6]. First we obtain upper bounds on graph orientations with fixed outdegree by enhancing the existing graph theoretic tools. Then we use the relation between graph orientations and the bound on the embedding number to provide new upper bounds in all dimensions on the number of complex embeddings by extending the recent progress. Namely, for $d = 2$ (Laman graph embeddings) and $d = 3$, we improve the upper bound from $O(3.78^{|V|})$ to $O(3.46^{|V|})$ and from $O(6.84^{|V|})$ to $O(6.32^{|V|})$, respectively.

Regarding the tightness of our results, we present examples of graphs indicating that our bound on the outdegree-constrained orientations may be sharp, but we have no similar data for the embedding number.

**Keywords** — Graph embedding, Graph orientation, Minimally rigid graph, Laman graph, Upper bound

## 1 Introduction

Rigidity theory studies the properties of graphs that can have rigid embeddings in a specified embedding space. Besides being a mathematical area with significant research interest, it has also received much attention due to its applications in molecular biology [17], robotics [22], and architecture [2, 11].

Let $G$, be a simple undirected graph and $\mathbb{R}^d$ be the embedding space. We will denote by $V(G)$ and $E(G)$ respectively the set of vertices and edges of $G$, while $G[V']$ denotes the subgraph of $G$ induced by a subset of vertices $V' \subseteq V(G)$. An embedding of $G$ in $\mathbb{R}^d$ is an assignment of the vertices of $G$, to a configuration in $\mathbb{R}^d$, $\mathbf{p} = \{p_1, \dots, p_{|V|}\} \in \mathbb{R}^{d|V|}$. A graph $G$ and a configuration $\mathbf{p}$ constitute a framework $G(\mathbf{p})$ in $\mathbb{R}^d$. In the case of simple undirected graphs, these frameworks are called bar (or bar-joint) frameworks [20]. Every framework induces a bilabelled set of edge lengths $\lambda = (\|p_u - p_v\|)_{(u,v) \in E}$, that are called bars. An embedding (and its corresponding framework) is *rigid* if and only if it admits a finite number of embeddings that satisfy the edge lengths, up to rigid motions; otherwise it is *flexible*. In fact, rigidity or flexibility is a generic property of the underlying graph, since *generically rigid graphs* are rigid for any edge lengths induced by a generic embedding [1]. We are particularly interested in the class of *generically minimally rigid graphs*, that correspond to well-constrained algebraic systems. A graph $G = (V, E)$ is generically minimally rigid if it is generically rigid and $G - e$ is flexible for all $e \in E$. Any graph that is generically minimally rigid in $\mathbb{R}^d$ is also generically minimally rigid in $S^d$ [21] and $\mathbb{C}^d$. In the sequel, whenever we refer to bounds on euclidean spaces, spherical spaces are also implied.

An important theorem in graph rigidity, due to Maxwell, provides us a necessary condition for a graph to be minimally rigid. More precisely, every minimally rigid graph in $\mathbb{R}^d$ has $|E| = d \cdot |V| - \binom{d+1}{2}$ edges, while for any
subgraph $G' \subseteq G$ with $V(G') \ge d$ the inequality $|E(G')| \le d \cdot |V(G')| - \binom{d+1}{2}$ holds [18]. This condition is also sufficient for the case of $d=2$ [16, 19], but not for higher dimensions. Minimally rigid graphs in dimension 2 are well-known as *Laman graphs*. It has been proposed to call minimally rigid graphs in dimension 3 "Geiringer graphs" [3, 13].

From an algebraic point of view, the number of embeddings for a graph (or simply embedding number) given an induced edge length set corresponds to the solutions of an algebraic system constrained by this set. The complex solutions of such a system extend the notion of the embedding to the complex space, thus allowing us to employ tools from the complex algebraic geometry, since the embedding number of $G$ in $\mathbb{R}^d$ is obviously bounded from above by the number of complex solution of the corresponding algebraic system, and by bounds on this number.

An open question on graph rigidity is to obtain tight upper bounds on the number of embeddings of minimally rigid graph in $\mathbb{R}^d$ (or $\mathbb{C}^d$). An immediate result from the application of Bézout's theorem to the corresponding algebraic system of a graph, is a trivial bound of $O(2^{d|V|})$ for a graph $G = (V, E)$.

*Existing work.* In previous years, the best upper bound was delivered in [9], using a theorem on the degree of determinantal varieties [15] on the Cayley-Menger embeddability conditions [8]. This bound did not improve the exponential asymptotic order of the Bézout bound, while the lower bounds on the maximal embedding number that have been computed are far from it. More precisely, in the real case it has been proven that there are graphs with $\Omega(2.3780^{|V|})$ embeddings in the case of $\mathbb{R}^2$, $\Omega(2.5198^{|V|})$ embeddings in $\mathbb{S}^2$ and $\Omega(2.6553^{|V|})$ in $\mathbb{R}^3$ [3], while in the complex case the bounds are respectively $\Omega(2.5080^{|V|})$ [10, 13], $\Omega(2.5698^{|V|})$ [12], and $\Omega(3.0683^{|V|})$ [13].

Recently, an approach relating the multi-homogeneous Bézout bound for certain algebraic systems with outdegree-constrained graph orientations and matrix permanents [4] was used to improve the bound on the embedding number for dimensions $d \ge 5$. Subsequently, an elimination process that bounds the above-mentioned orientations managed to improve the trivial bound for the first time in dimensions 2 and 3 proving that there the embedding number is at most $O(3.78^{|V|})$ and $O(6.84^{|V|})$ respectively [6]. This method improved also upon the results of [4] for bigger dimensions.

*Our Contribution.* In this work, we manage to further decrease the asymptotic order of the upper bound for all dimensions $d \ge 2$. As in [6], we apply an elimination process on a graphical structure to obtain upper bounds on the number of outdegree-constrained orientations for fixed $d$. In particular, we harness Maxwell's condition in order to restrict the degree of the eliminated vertices. We also treat vertices of certain degree profiles with a different approach from [6]. More precisely, we use a delicate method relating certain sequences with the elimination of a path of vertices with these degree profiles and subsequently we establish bounds on orientations with certain outdegree. The bounds on the orientations yield improved upper bounds on the embedding number. For the case of $d=2$, our upper bound on the embedding number is of $O(3.46^{|V|})$, while for Geiringer graphs the new upper bound is $O(6.32^{|V|})$. Finally, we prove that there are graphs that can have outdegree-constrained orientations approaching the bound of the orientations, when the outdegree for all vertices of our graphical structure is 2.

*Organization.* We structure the rest of the paper as follows. In Section 2, initially we provide some basic concepts presented previously in [4, 6]. Subsequently, we give some definitions and technical lemmas that will be used later for the elimination of vertices with certain degree profiles. In Section 3, we provide detailed description of our elimination process in the case of dimension 2, establishing the new upper bound. This case shall serve as basis for some induction hypotheses in higher dimensions. In Section 4, we provide new upper bounds for $d \ge 3$ generalizing the results for Laman graphs. Then, in Section 5 we give examples of Laman graphs that have the biggest number of orientations among the cases we computed. These results give a higher significance on the tightness of our bound on the number of outdegree-constrained orientations. Finally, in Section 6 we conclude and present some ideas that could extend the present research.

## 2 Preliminaries

In this section, we initially present the relation between graph orientations and the bound on the embedding number introduced in [4], then some basics on the elimination process used in [6]. The elimination process removes either single vertices, or groups of vertices. Recall that a $d$-clique, denoted $K_d$, is a complete graph of $d$ vertices.

We start with a theorem [4, Thm.3], essential in our approach. We have adapted the statement to cover the case of absence of $K_d$ given a minimally rigid graph in $\mathbb{C}^d$; see [4, 6] for more detail on this.

**Theorem 1** ([4]). Let $G = (V, E)$ be a minimally rigid graph in $\mathbb{C}^d$ that contains a $K_{d'}$, $d' \le d$, called fixed $K_{d'}$, while $V(K_{d'})$ are the fixed vertices. If $d' < d$, let $V' = \{v_{d'+1}, \dots, v_d\} \subseteq V$ be a set of vertices, called partially
fixed vertices, which is disjoint from $V(K_{d'})$; if $d' = d$, then $V' = \emptyset$. Let also $\mathcal{R}(G, K_{d'}, V')$, denote the number of outdegree-constrained orientations of $G' = (V, E \setminus E(K_{d'}))$, such that:

* the outdegree of vertices $V(K_{d'})$ is 0.

* if $d' < d$, then the outdegree of the partially fixed vertices $v_{d'+1}, \dots, v_d$ is $d'$, $\dots, d-1$, respectively.

* the outdegree of every vertex in $V \setminus (V(K_{d'}) \cup V')$ is $d$.

Then the embedding number of $G$ in $\mathbb{C}^d$, is bounded from above by the following quantity:

$$mBe(G, K_{d'}, V') = 2^{|V|-d} \cdot \mathcal{R}(G, K_{d'}, V').$$

The bound of this theorem is actually the multihomogeneous Bézout (m-Bézout) bound of an algebraic system, whose number of solutions corresponds to the embedding number (see [4] for details). In the case $d=2$, there is always a fixed edge $K_2$, so $V' = \emptyset$. For Geiringer graphs, although in most known cases there exists at least one triangle, there are graphs such as $K_{6,4}$ with no such subgraph. When $V' = \emptyset$, we omit $V'$, and write $mBe(G, K_d)$ and $\mathcal{R}(G, K_d)$ to denote the bound of Theorem 1 and the number of the orientations, respectively. The outdegrees in this theorem represent the number of coordinate variables per vertex in the underlying algebraic system [6]. All other coordinates are fixed.

This theorem relates the embedding number of a minimally rigid graph $G$ and the number of its orientations. Hence, bounding the number of orientations immediately yields bounds on the embedding number by applying Theorem 1. In this work, we provide tighter upper bounds on the number of orientations, hence better upper bounds on the embedding number, for the class of minimally rigid graphs. For this, following [6], we use a graphical structure called pseudograph.

**Definition 2.** A pseudograph $J$ is a triplet $(V_J, E_J, H_J)$, such that $V_J$ denotes the set of vertices, $E_J$ denotes the set of normal edges incident to two vertices, and $H_J$ denotes a set of edges, called hanging edges, that are incident to only one vertex in $V_J$. The hanging edges are directed outwards.

Let $J = (V_J, E_J, H_J)$ be a pseudograph. A sub-pseudograph of $J$, is a pseudograph formed by subsets of $V_J, E_J$, and $H_J$. In the sequel, given a sub-pseudograph $J'$, we denote by $V(J')$, $E(J')$ and $H(J')$ the vertices, the normal edges and the hanging edges of $J'$ respectively. We also denote by $J[V']$ the sub-pseudograph induced by a subset of vertices $V' \subseteq V_J$. Every vertex $v$ of a pseudograph has a degree profile $(r, h)$, where $r$ denotes the number of the normal edges that are incident to $v$, and $h$ denotes the number of the hanging edges that are incident to $v$. Also, we refer to $r$ as the normal degree of $v$, and to $h$ as the hanging degree of $v$.<fnref n="1" /> The simple undirected graph $J^* = (V_J, E_J)$ is the normal subgraph of $J$.

To bound the embedding number, we relate graph orientations in Theorem 1 to pseudograph orientations. This is achieved by the following construction (see Figure 1). Let $G = (V, E)$ be a minimally rigid graph, $K_{d'}$ and $V'$ as defined in Theorem 1. Then we consider the pseudograph $J = (V_J, E_J, H_J)$, such that $V_J = V \setminus V(K_{d'})$, $E_J = \{e = (u, v) \in E | u \notin V(K_d) \land v \notin V(K_d)\}$. The hanging edges represent the connections of a vertex $v$ with $V(K_{d'})$ and the outdegree of partially fixed vertices $V'$ in the initial graph. If $V' \neq \emptyset$, then for every partially fixed vertex $v$ with outdegree $d$, we shall consider $d - \tilde{d}$ hanging edges. Now, the number of orientations of $J$ such that every vertex has outdegree $d$ equals $\mathcal{R}(G, K_{d'}, V')$. These shall be called valid $d$-orientations, while every connected component of a pseudograph constructed as described above shall be a connected $d$-pseudograph. Pseudographs derived by removing a vertex of a $d$-pseudograph are also considered $d$-pseudographs. Let us remark that if a vertex $v$ has degree profile $(r, h)$ with $r+h < d$ or $h > d$, then it has no valid $d$-orientation, since in the first case its outdegree is strictly smaller than $d$, while in the latter case it has already outdegree larger than $d$. Let us also recall the following result, namely [6, Prop.3.2], which gives a Maxwell-like count on $d$-pseudographs.

**Lemma 3** ([6]). If a pseudograph $J = (V_J, E_J, H_J)$ has a valid $d$-orientation, then $d \cdot |V_J| = |H_J| + |E_J|$.

This construction may result to multiple connected components, but in our analysis it suffices to bound the $d$-orientations of all connected $d$-pseudographs. In the following sections, we apply an elimination process to the vertices of such pseudographs that refines the techniques in [6].

Before describing the main aspects of the elimination process, let us introduce a family of useful sub-pseudographs.

**Definition 4.** Let $J$ be a pseudograph. The set $\mathcal{F}_{d,J}$ contains pairs $(\mathcal{J}_d, v_0)$ of connected sub-pseudographs of $J$ and vertices of them, respectively. A sub-pseudograph $\mathcal{J}_d$ is contained in $\mathcal{F}_{d,J}$ if all of the following hold:

<footnote n="1">¹In [6], 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.</footnote>
<figure><img src="image_2.png" /><figcaption>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).</figcaption></figure>

* $\mathcal{J}_d$ has at least 2 vertices and no cycles,

* $J - \mathcal{J}_d$ is connected,

* $v_0$ is the leading vertex of $\mathcal{J}_d$. This is a non-cut vertex and it is always connected with other vertices in $J - \mathcal{J}_d$. All the other vertices of $\mathcal{J}_d$ are the non-leading vertices,

* all vertices have normal degree $2d - 1$, except possibly $v_0$.

Sub-pseudographs $\mathcal{J}_d$ are used to include path elimination steps in the elimination process. Path elimination steps also appear in [6], but here we use different paths that eventually improve the bound. The leading vertex of a $\mathcal{J}_d$ is the vertex that is the first to be removed, during the elimination of its corresponding sub-pseudograph $\mathcal{J}_d$.

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

i. single vertex elimination steps, and

ii. path elimination steps,

which are subject to different methods for bounding the orientation number. In both cases the resulting pseudograph remains connected.

The single vertex elimination step is the same as in [6]: Given a pseudograph $J$ and a vertex $v$ with degree $(r, h)$, all hanging edges of $v$ are removed. Its normal edges are either removed or become hanging edges incident to their other endpoint. In order to satisfy the count of Lemma 3, the resulting pseudographs shall have totally $d$ fewer normal edges and hanging edges. Since hanging edges are incident only to $v$, then $h$ hanging edges are removed. Now let $e = (v, u)$ be a normal edge incident to $v$ in $J$. It shall be either totally removed in the resulting pseudograph or become a hanging edge incident to $u$. So, $d-h$ normal edges are removed, while the other $r-h$ normal edges become hanging (see Figure 4).

Path elimination steps are actually consecutive single vertex elimination steps. We differentiate the two types of steps, because in the latter, vertices of different hanging degree profiles are used so as to yield tighter bounds.

During elimination, removal of $v$ from $J$ corresponds to the orientation of its incident edges. If edge $e = (v, u)$ is outdirected from $v$, it is also removed in the next step of the elimination. If $e$ is directed inwards $v$, then it remains in the next step as a hanging edge incident only to $u$.

<figure><img src="image_3.png" /><figcaption>Figure 2: An example sub-pseudograph $\mathcal{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$.</figcaption></figure>
This process has the following stopping condition, already used in [6, Prop.3.7].

**Lemma 5 ([6]).** Let $J = (V_J, E_J, H_J)$ be a pseudograph such that its normal subgraph $J^* = (V_J, E_J)$ is a tree. Then (i) the number of valid orientations of $J$ is either 1 or 0, and (ii) if $G$ has a valid orientation, then $|H_J| = (d-1) \cdot |V_J| + 1$, where $d$ is the fixed outdegree required.

This count is derived from the relation $|E_J| = |V_J| + 1$ between the edges and the vertices of a tree and the count of Lemma 3. Notice that if we allowed the elimination of cut vertices, then the edge count for $g$ connected trees would be $|E_J| = |V_J| + g$, so the relation between the hanging edges and the vertices would become $|H_J| = (d-1) \cdot |V_J| + g$. In order to restrict the parameters of the bound in our analysis only to total number of vertices and hanging edges, we prefer to keep the pseudograph connected throughout the elimination process.

Now we show that there is always an elimination process that does not create more connected components of the $d$-pseudographs. Additionally, we impose certain restrictions on the normal degree of the removed vertex. For that reason, let us recall the definition of the block-cut tree. This definition is necessary to prove the existence of non-cut vertices with bounded normal degree.

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

We may use the same definition for the block-cut tree (see Figure 3) of the normal subgraph of every pseudograph.

<figure><img src="image_4.png" /><figcaption>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.</figcaption></figure>

The following lemma uses Maxwell's condition and Definition 6 to bound the normal degree of the eliminated vertices.

**Lemma 7.** Let $J = (V_J, E_J, H_J)$ be a connected $d$-pseudograph derived from a minimally rigid graph $G$, as described above. Then $J$ has at least one non-cut vertex with normal degree smaller than or equal to $2d-1$.

*Proof.* Let $J^* = (V_J, E_J)$ denote the normal subgraph of $J$. Since $J^* \subseteq G$, Maxwell's condition holds for every subgraph $J'$ of $J^*$, so we get that $|E(J')| \le d \cdot |V(J')| - \binom{d+1}{2}$. Consider a leaf of the block-cut tree $B_{J^*}$. We denote the vertices of the biconnected component that corresponds to a leaf of $B_{J^*}$ by $L$. The sum of normal degrees for all vertices in $J^*[L]$ is at most $2d \cdot |V(J^*[L])| - 2\binom{d+1}{2}$. In it, there is at most one vertex which is a cut-vertex of $J^*$, because $B_{J^*}$ is a biconnected component. The cut vertex has normal degree at least 2 in $J^*[L]$. Assume that the smallest normal degree for a non-cut vertex in the leaf is $2d$. Then, it follows that the sum of normal degrees for all vertices in $J^*[L]$ is at least $2d \cdot |V(J^*[L])| - 2(d-1)$, violating Maxwell's condition. This leads to a contradiction, because Maxwell's condition shall be satisfied for $J^*[L]$, so there are always vertices with normal degree smaller or equal to $2d-1$.

Throughout the elimination process this property holds, since the normal subgraph of any pseudograph derived from an elimination step is always a subgraph of a minimally rigid graph. $\square$

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.
In order to exploit the elimination process to bound the number of d-orientations, we need to define two quantities for every elimination step. These are first defined in the case of the single vertex elimination step and specialized for path elimination steps. Let $J$ be a pseudograph in which vertex $v$ is eliminated. Then the number of ways to choose the normal edges that remain in the resulting pseudograph as hanging edges corresponds to different resulting pseudographs that may have valid $d$-orientations. This number is the cost of the elimination step. Notice that the only requirements for the elimination process are the connectivity and the edge count of Lemma 3. Since the latter is a necessary condition (and not always sufficient) for the existence of a valid $d$-orientation, this means that some of the choices may result to pseudographs with no orientations. This means that the cost in each elimination step bounds the number of valid orientations for the edges incident to the vertex that is to be eliminated in this particular step. This bound depends on the degree profile of this vertex, as well as the combinatorial properties of the pseudograph. Let us remark, that the cost of multiple steps has multiplicative effect: if eliminating the vertex $v_1$ from $J$ has cost $c_1$ and in the next step $v_2$ is eliminated with cost $c_2$, then the total number of orientations for these two steps is bounded by $c_1 \cdot c_2$. In other words, the cost of the removal of a vertex $v$ expresses the quotient of the number of valid orientations of $J$ over the maximum number of valid orientations of the resulting pseudographs. This property will be used in the case of path elimination to refine our analysis. Let us comment here the main difference in our analysis between path elimination step and single vertex elimination step: when eliminating two consecutive vertices $v_1$ and $v_2$ in the first case we consider for $v_2$ the cost from all resulting pseudographs, while in the second case we consider for $v_2$ only the resulting pseudograph in which the cost of $v_2$ is maximized. Finally, we remark that the total cost of the elimination process bounds the number of orientations.

A second quantity we use is the *hanging edges equilibrium*, which is the difference between hanging edges in the resulting pseudographs and in $J$. This gives a hint about how fast the elimination process may approach the tree condition: for each vertex elimination the number of vertices in the resulting pseudograph drops by 1, but the 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).

The exact formulas for these quantities were given in [6, Prop. 3.4] as follows:

**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 elimination of a vertex $v$ is denoted with $C_d(r, h)$ and is given by the formula:

$$C_d(r, h) = \binom{r}{d-h}, \qquad (1)$$

while the hanging edges equilibrium shall be denoted with $H.E.E.$:

$$H.E.E. = r - d \qquad (2)$$

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

These general aspects of the elimination process were also used in [6]. Now we will present some new clues and concepts that will lead to the improved bounds eliminating sub-pseudographs $J_d$ (see Definition 4).

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

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

$$\binom{r-1}{d-h} \text{ and } \binom{r-1}{d-h-1} \qquad (3)$$

ways in which $u$ acquires, and does not acquire a hanging edge, respectively, after the elimination of $v$.

*Proof.* Let us consider that $u$ gets a hanging edge after the elimination of $v$. That means that the edge $e = (u, v)$ is directed towards $v$, so $d-h$ edges incident to $v$ shall be directed outwards it. The available edges after the orientation of $e$ are $r-1$, indicating that there are $\binom{r-1}{d-h}$ ways to orient them. Since the cost for the elimination

of $v$ is $\binom{r}{d-h}$, by Pascal's identity we derive the count for the case that $u$ does not get a hanging edge. $\square$
<figure><img src="image_5.png" /><figcaption>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 $\binom{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 is $\binom{3}{3-2} = 3$ and every neighbour acquires a hanging edge in 2 scenarios.</figcaption></figure>

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

Now we present the basic aspects of path elimination. Notice that path vertex elimination steps were also used in [6]. Here, we take a different approach and alter the method in order to group vertices of different hanging degree, but same normal degree.

We denote by $C_d(\ell)$ the cost for the elimination of a sub-pseudograph $\mathcal{J}_d$ with $\ell + 1 \ge 2$ vertices. The leading vertex $v_0$ has a particular degree profile $(r, h)$. We will consider principally the case that $r = 2d - 1$, leading vertices with different normal degree are considered only in Lemma 22. All the other vertices have the same normal degree, $2d - 1$, in $\mathcal{J}_d$ before the elimination. Now, the elimination of $\mathcal{J}_d$ can be seen as consecutive single vertex elimination steps. Thus, after the elimination of $v_0$, $v_1$ has a drop in normal degree by 1 and will be eliminated as a vertex with normal degree $2d - 2$. This will happen for all vertices in $\mathcal{J}_d$, but for $v_0$. On the other hand, these vertices do not have a standard hanging degree, since the distribution of hanging edges in the resulting pseudographs follows the count of Lemma 9 (see Figures 5 and 6 for examples).

In the analysis for the total cost of a pseudograph $J$, we separate the case of the leading vertex $v_0$ with degree profile $(r, h)$ and the non-leading vertices $\mathcal{J}_d - \{v_0\}$. For the first one, we consider the cost $C_d(r, h)$ as in the case of single vertex elimination step. In order to compute $C_d(\ell)$, we use the formula of Lemma 8 taking into account every possible scenario for the degree profile of the non-leading vertices. If it is required, we may use an upper bound for the cost of $v_0$, which is the *effective cost* and equals to $C_d^*(r) = \max_{0 \le h \le d} C_d(r, h)$. For the other vertices, we need to introduce the following definition, which is a variant of the definition of the cost for single vertices.

**Definition 10.** Let $\mathcal{J}_d = (v_0, v_1, \dots, v_\ell)$ be a path of $\ell + 1$ vertices, as in Definition 4, with $\ell \ge 1$. Let $C_d(\ell)$ be the total cost of removing these vertices in order. The *average cost* of removing the path without the first vertex $v_0$ is

$$ \left( \frac{C_d(\ell)}{C_d(0)} \right)^{1/\ell} $$

where $C_d(0)$ is the cost of the removal of $v_0$.

Moreover if there is an *effective cost* $C_d^*(0)$ for $C_d(0)$, then the ratio

$$ \left( \frac{C_d(\ell)}{C_d^*(0)} \right)^{1/\ell} $$

is the *eliminating average cost*.
This shall be considered the cost for each vertex in $\mathcal{J}_d - \{v_0\}$. This modifications are necessary, since if vertices with degree profile $(2(d-h), h)$ for $1 \le h \le d-1$ were always eliminated with a single vertex elimination step, then the analysis would lead to bigger bounds on $d$-orientations. The eliminating average cost is used when we want to bound effectively the process by using an upper bound in the case of $C_d(0)$, instead of the exact cost. A necessary condition when using the average cost is that the H.E.E. is not altered by these changes, compared with the case of single vertex elimination. This happens because H.E.E. depends only on normal degree (see Equation 2). The eliminating average cost is used to decrease the ratio of the average cost. The cost for the path elimination is not affected by this modification: setting $C_d^*(0)$ as the cost for $v_0$ and $(\frac{C_d(\ell)}{C_d^*(0)})^{1/\ell}$ as the cost for all the other vertices in $\mathcal{J}_d - \{v_0\}$, the total cost is remains $C_d(\ell) = C_d^*(0) \cdot \left(\left(\frac{C_d(\ell)}{C_d^*(0)}\right)^{1/\ell}\right)^2$.

In the sequel, we present some technical lemmas, defining certain sequences and a bound on them. The reason why we define here $C_d$, $\mathcal{B}_d$ and $\mathcal{G}_d$ is to show that the total cost of our paths (in the worst case scenario) follows the pattern of the recursive sequences given in these lemmas. This is done in Sections 3 and 4. First, we define $\mathcal{B}_d$ and $\mathcal{G}_d$ recursively. Then, we define $C_d$ using these functions and prove a new recursive formula on $C_d$.

**Lemma 11.** Let $\mathcal{B}_d(\ell)$ and $\mathcal{G}_d(\ell)$ be the following recursive functions:

$$ 
\begin{aligned}
\mathcal{B}_d(\ell+1) &= \frac{\alpha_d}{2} \cdot (\mathcal{B}_d(\ell) + \mathcal{G}_d(\ell)) \\
\mathcal{G}_d(\ell+1) &= \frac{\alpha_d}{2} \cdot \mathcal{B}_d(\ell) + \left(\beta_d - \frac{\alpha_d}{2}\right) \cdot \mathcal{G}_d(\ell)
\end{aligned}
\quad (4) $$

where $\alpha_d = \binom{2d-2}{d-1}$ and $\beta_d = \binom{2d-2}{d}$, and $d \ge 2$.

Given these functions we define the sequence

$$ C_d(\ell) = \alpha_d \mathcal{B}_d(\ell) + \beta_d \mathcal{G}_d(\ell). \quad (5) $$

Then $C_d(\ell)$ is defined recursively for $\ell \ge 1$ by:

$$ C_d(\ell+1) = \beta_d \cdot C_d(\ell) + \frac{\alpha_d(\alpha_d - \beta_d)}{2} \cdot C_d(\ell-1) \quad (6) $$

Proof.

$$ 
\begin{aligned}
C_d(\ell+1) &= \alpha_d \mathcal{B}_d(\ell+1) + \beta_d \mathcal{G}_d(\ell+1) \\
&= \frac{\alpha_d^2}{2} (\mathcal{B}_d(\ell) + \mathcal{G}_d(\ell)) + \frac{\alpha_d \beta_d}{2} \mathcal{B}_d(\ell) + \beta_d (\beta_d - \frac{\alpha_d}{2}) \mathcal{G}_d(\ell) \\
&= \frac{\alpha_d^2}{2} (\alpha_d \mathcal{B}_d(\ell-1) + \beta_d \mathcal{G}_d(\ell-1)) + \frac{\alpha_d \beta_d}{2} (\mathcal{B}_d(\ell) - \mathcal{G}_d(\ell)) + \beta_d (C_d(\ell) - \alpha_d \mathcal{B}_d(\ell)) \\
&= \frac{\alpha_d^2}{2} C_d(\ell-1) + \beta_d C_d(\ell) - \frac{\alpha_d \beta_d}{2} (\mathcal{B}_d(\ell) + \mathcal{G}_d(\ell)) \\
&= \beta_d \cdot C_d(\ell) + \frac{\alpha_d(\alpha_d - \beta_d)}{2} \cdot C_d(\ell-1)
\end{aligned}
$$

□

In the sequel we set $\mathcal{B}_d(0) = \mathcal{G}_d(0) = 1$ as initial condition for these sequences. Notice that by the definition of the sequences in equation 4, we have that $\mathcal{B}_d(\ell) > \mathcal{G}_d(\ell)$, since $\alpha_d > \beta_d$, for all $\ell \ge 1$.

Now we are ready to bound the ratio of two consecutive terms of the sequence $C_d(\ell)$. This is used to bound the cost of vertices eliminated with a path elimination step.

**Lemma 12.** For all $\ell \ge 0$ and $d \ge 2$ the ratio $\frac{C_d(\ell+1)}{C_d(\ell)}$ is strictly bounded from above by

$$ \mathcal{D}(d) = \frac{\alpha_d^2 + \beta_d^2}{\alpha_d + \beta_d}, $$

given that $\mathcal{B}_d(0) = \mathcal{G}_d(0) = 1$.

<footnote n="2">²Note that $\max_{0 \le h \le 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).</footnote>
Proof. First, we will prove that it holds for $\ell \ge 4$, and then we will prove it for the 4 starting cases.

$$ 
\begin{align*}
\frac{C_d(\ell+1)}{C_d(\ell)} &\le \frac{\alpha_d^2 + \beta_d^2}{\alpha_d + \beta_d} &\iff \\
(\alpha_d + \beta_d) \cdot C_d(\ell+1) &\le (\alpha_d^2 + \beta_d^2) \cdot C_d(\ell) &\iff \\
\alpha_d \beta_d C_d(\ell) + \beta_d^2 C_d(\ell) + \frac{\alpha_d(\alpha_d - \beta_d)(\alpha_d + \beta_d)}{2} \cdot C_d(\ell-1) &\le \alpha_d^2 C_d(\ell) + \beta_d^2 C_d(\ell) &\iff \\
(\alpha_d + \beta_d) \cdot C_d(\ell-1) &\le 2 \cdot C_d(\ell) &\iff \\
(\alpha_d + \beta_d) \cdot C_d(\ell-1) &\le 2\beta_d \cdot C_d(\ell-1) + \alpha_d(\alpha_d - \beta_d) \cdot C_d(\ell-2) &\iff \\
C_d(\ell-1) &\le \alpha_d \cdot C_d(\ell-2) &\iff \\
\beta_d \cdot C_d(\ell-2) + \frac{\alpha_d(\alpha_d - \beta_d)}{2} \cdot C_d(\ell-3) &\le \alpha_d \cdot C_d(\ell-2) &\iff \\
\alpha_d \cdot C_d(\ell-3) &\le 2 \cdot C_d(\ell-2) &\iff \\
\alpha_d \cdot C_d(\ell-3) &\le 2\beta_d \cdot C_d(\ell-3) + \alpha_d(\alpha_d - \beta_d) C_d(\ell-4) &\iff \\
(\alpha_d - 2\beta_d) \cdot C_d(\ell-3) &\le \alpha_d(\alpha_d - \beta_d) \cdot C_d(\ell-4) &
\end{align*}
$$

For $C_d(1)/C_d(0)$, we simply use the definition $C_d(\ell+1) = \alpha_d B(\ell+1) + \beta_d G(\ell+1)$, for $\ell = 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:

$$ \frac{C_d(1)}{C_d(0)} = \frac{\alpha_d^2 + \beta_d^2}{\alpha_d + \beta_d}. $$

For the case of $C_d(2)/C_d(1)$, we stop at the inequality (7) above, for $\ell = 1$, and we have

$$ 
\begin{align*}
(\alpha_d + \beta_d) \cdot C_d(0) &\le 2 \cdot C_d(1) \\
(\alpha_d + \beta_d)^2 &\le 2 \cdot (\alpha_d^2 + \beta_d^2) \\
(\alpha_d - \beta_d)^2 &\ge 0
\end{align*}
$$

$$ 
\begin{align*}
C_d(1) &\le \alpha_d \cdot C_d(0) \\
\alpha_d^2 + \beta_d^2 &\le \alpha_d^2 + \alpha_d \beta_d
\end{align*}
$$

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

$$ 
\begin{align*}
\alpha_d \cdot C_d(0) &\le 2 \cdot C_d(1) \\
\alpha_d \beta_d &\le \alpha_d^2 + 2\beta_d^2
\end{align*}
$$

Notice that setting $B(0) = G(0) = 1$, as stated above, we get $C_d(0) = \alpha_d + \beta_d$. Furthermore, using equations 4 and 6, we get $C_d(1) = \alpha_d^2 + \beta_d^2$. 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.

$$ \left( \frac{C_d(\ell)}{C_d(0)} \right)^{1/\ell} \le \left( \frac{C_d(1)}{C_d(0)} \right)^{1/\ell}, $$

<footnote n="287">287 which is true since $\alpha_d \le 2\beta_d$ for $d \ge 2$ and the other factors are positive.</footnote>

<footnote n="288">288 Now, we should check whether it holds for the remaining cases, i.e. for $C_d(1)/C_d(0)$, $C_d(2)/C_d(1)$, $C_d(3)/C_d(2)$,</footnote>

<footnote n="289">289 and $C_d(4)/C_d(3)$.</footnote>

<footnote n="290">290 which is true.</footnote>

<footnote n="291">291 For the case $C_d(3)/C_d(2)$, we stop at the inequality (8), for $\ell = 2$:</footnote>

<footnote n="292">292 which is true, since $\alpha_d \ge \beta_d$.</footnote>

<footnote n="293">293 which is clearly true. $\square$</footnote>
## 3 Laman Graphs

In this section, we develop a method that improves the existing upper bounds on the embedding number of Laman graphs, which are the minimally rigid graphs in dimension 2. The analysis for this dimension is simpler than the ones regarding higher dimension and serves as base case for higher dimensions. Our method relies on Theorem 1, which relates the bound on the embedding number with the outdegree-constrained orientations. In this section we can remove subscripts referring to the embedding space from $\mathcal{F}_{d,J}, \mathcal{J}_d, C_d, \alpha_d, \beta_d$. Additionally, the leading vertex $v_0$ for all paths $\mathcal{J}$ has only normal degree 3, that is exactly $2d-1$ in the case of $d=2$.

We use an elimination process similar to [6] in order to improve the upper bound. We recall that the tree condition (Lemma 5) signifies the termination of the process. Given a pseudograph $J = (V_J, E_J, H_J)$ and setting $n = |V_J|$ and $k = |H_J|$, we have that this condition is satisfied if $k = n + 1$.

One of the main differences between the elimination method described here and the one in [6], is the restriction on the normal degree of the eliminated vertices. Specializing Lemma 7 to the case of $d=2$, we have that connected 2-pseudographs derived from the deletion of a fixed edge in a Laman graph always contain a non-cut vertex with normal degree less or equal to 3. This also happens for all connected pseudographs that evolve through the elimination process, signifying that those that have valid 2-orientations may have vertices with the following vertex profiles, cost and H.E.E. (see Equation 1):

* Vertices with normal degree 1 have H.E.E. = -1: (1, 2), (1, 1), with cost=1.

* Vertices with normal degree 2 have H.E.E.= 0: (2, 2), (2, 0), with cost = 1, and (2, 1), with cost = 2.

* Vertices with normal degree 3 have H.E.E.= 1: (3, 2), with cost = 1, and (3, 0), (3, 1), with cost = 3.

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

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

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

* had already normal degree 2 in $J$.

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

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

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

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

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

**Lemma 14.** *There is always an elimination process such that all composite non-cut vertices with normal degree 2 are created after the elimination of a vertex of a sub-pseudograph $\mathcal{J}$ in $\mathcal{F}_J$.*

*Proof.* The only way to create a vertex with normal degree 2 is by eliminating the neighbour of a vertex with normal degree 3. By Definition 4, if the eliminated vertex has also degree 3, or is a composite vertex, then it belongs to $\mathcal{F}_J$, so our case holds.

If at a certain instance of the elimination there are no vertices with normal degree 3 there is nothing to prove. If the vertices with normal degree 3 are all cut vertices, then we can continue the elimination process eliminating a vertex that lies in the leaf of the block cut tree containing this cut vertex. By Lemma 7 there is always a non-cut vertex $u$ in this biconnected component, with normal degree smaller than 3. If the cut vertex $v$ has normal degree 3 and $u$ has normal degree 1, then after its elimination $v$ is a non-composite vertex. If $u$ has normal degree 2, then $v$ remains a cut vertex and cannot be eliminated before a further drop of degree in one of the next elimination steps. $\square$
It is clear from Definition 4, that all vertices of $\mathcal{J}$ but the leading vertex $v_0$ are eliminated with normal degree 2, since when one vertex is eliminated, then the normal degree for all its neighbours drops by 1 in the resulting pseudograph. The following corollary shows how we can bound the average cost of such paths in the case of Laman graphs.

**Lemma 15.** *The eliminating average cost for the elimination of composite vertices can be set as less or equal to 5/3. This is a specialization of Lemma 12 for $d = 2$.*

*Proof.* We show that the worst case scenario for the total and the average cost is covered by Equation 6 that results from the recursive Equations 4 (see Lemma 9 for details). Let $C(\ell)$ denote the cost of elimination for the first $\ell + 1$ vertices of a sub-pseudograph $\mathcal{J} \in \mathcal{F}_J$. Let also $\mathcal{B}(\ell)$ denote the number of pseudographs with a (2, 1) vertex to be eliminated and $\mathcal{G}(\ell)$ the number of pseudographs with a (2, 0) or (2, 2) vertex (which is a trivial vertex) to be eliminated, when $\ell \ge 1$. Then, we have that $C(\ell) = 2\mathcal{B}(\ell) + \mathcal{G}(\ell)$, since the cost of a trivial vertex is 1, while the cost for a non-trivial one is 2. This definition for $C(\ell)$ is a specialization of Equation 5 in the case of $d = 2$, if we substitute $\mathcal{C}_2$ with $\mathcal{C}$, $\mathcal{B}_2$ with $\mathcal{B}$ and $\mathcal{G}_2$ with $\mathcal{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 $\mathcal{G}^*(\ell)$ the number of pseudographs with trivial vertices that create (2, 1) vertices and $\mathcal{G}'(\ell)$ the number of pseudographs with trivial vertices that create other trivial vertices. This implies that $\mathcal{G}(\ell) = \mathcal{G}^*(\ell) + \mathcal{G}'(\ell)$. So, for the next vertex in $\mathcal{J}$ (if such exists) we derive the following equations:

$$ \mathcal{B}(\ell + 1) = \mathcal{B}(\ell) + \mathcal{G}^*(\ell) $$

$$ \mathcal{G}(\ell + 1) = \mathcal{B}(\ell) + \mathcal{G}'(\ell) $$

leading to the following relation for the total cost of a path after the elimination of the next vertex:

$$
\begin{align}
C(\ell + 1) &= 2\mathcal{B}(\ell + 1) + \mathcal{G}(\ell + 1) \nonumber \\
&= 2\mathcal{B}(\ell) + 2\mathcal{G}^*(\ell) + \mathcal{B}(\ell) + \mathcal{G}'(\ell) \nonumber \\
&= 2\mathcal{B}(\ell) + (\mathcal{G}^*(\ell) + \mathcal{G}'(\ell)) + \mathcal{B}(\ell) + \mathcal{G}^*(\ell) \nonumber \\
&\le C(\ell) + \mathcal{B}(\ell) + \mathcal{G}(\ell) \tag{10} \\
&= C(\ell) + 2\mathcal{B}(\ell - 1) + \mathcal{G}^*(\ell - 1) + \mathcal{G}'(\ell - 1) \nonumber \\
&= C(\ell) + C(\ell - 1) \nonumber
\end{align}
$$

The last quantity proves that the cost function for $\mathcal{J}$ follows, in the worst case, function $\mathcal{C}_2$ in Lemma 11³.

We need to specify the different initial conditions of the path in order to prove that the total cost of the path permits to use $\mathcal{D}(2) = 5/3$ as an upper bound for the eliminating average cost. By Lemma 14, we consider only the elimination for paths of vertices in $\mathcal{J}$, so the initial vertices can have only normal degree 3. If $v_0$ is a (3, 0) or a (3, 1) vertex and has cost 3, then the sequence $C(\ell)$ in the worst case scenario is exactly the one of Lemma 11 for $d = 2$.

If $v_0$ is a (3, 2) vertex and $v_1$ is eliminated as a (2, 1) vertex, then the ratio $C(1)/C(0) = 2 > 5/3$. We overcome this situation by making use of the eliminating average cost setting that $C^*(0) = 3$, while $C(1)$ is not altered. This change cannot surpass the number of orientations in our analysis, since the total cost of the path is not altered. Furthermore, for single vertex elimination in the case of $r = 3$ we have already considered a bound for the cost of vertices with such normal degree, as mentioned before, which is 3. Since $C(1)$ is smaller than the respective value of the sequence in Lemma 11, the next terms will be also smaller, so the eliminating average cost for all vertices but the leading one is bounded by 5/3. □

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

**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} \cdot (2/3)^k. $$

*Proof.* We consider that throughout the elimination process there have been eliminated $t$ vertices with normal degree 3, $m$ non-composite (2, 1) vertices, $\ell$ vertices with normal degree 2 in paths $\mathcal{J}$, $s_2$ trivial non-composite vertices

<footnote n="3">³The worst-case scenario for the cost sequence in dimension 2 has the same recursive definition as the Fibonacci sequence.</footnote>
<figure><img src="image_6.png" /><figcaption>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 \cdot 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 \cdot 2 \cdot 2 = 12$.</figcaption></figure>

and $s_1$ vertices with normal degree 1. Recall that the elimination process stops when the tree condition is satisfied.

Neglecting trivial vertices, the total cost is bounded by

$$3^t \cdot 2^m \cdot (5/3)^\ell \qquad (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 - \ell - s_1 - s_2$$

$$k' = k + t - s_1$$

Since $n' + 1 = k'$, we conclude that

$$t \le \frac{n - k - m - \ell + 1}{2}.$$

This results to

$$\begin{align*}
3^t \cdot 2^m \cdot (5/3)^\ell &\le 3^{n/2} \cdot 3^{-k/2} \cdot 3^{-m/2} \cdot 3^{-\ell/2} \cdot 3^{1/2} \cdot 2^m \cdot \left(\frac{5}{3}\right)^\ell \\
&= 3^{n/2} \cdot \left(\frac{2}{3}\right)^k \cdot \left(\frac{5}{3^{3/2}}\right)^\ell \cdot 3^{1/2} \\
&\le 3^{n/2} \cdot \left(\frac{2}{3}\right)^k \cdot 3^{1/2}
\end{align*}$$

since $m$ is at most $k$ (as a consequence of Definition 13).

Thus, the asymptotic order for the number of valid orientations for a connected 2-pseudograph up to the number of its vertices $n$ is $O(3^{n/2})$. Subsequently we have that given a pseudograph $J$ derived from a Laman graph with $g$
<figure><img src="image_7.png" /><figcaption>Figure 6: Another example of a $\mathcal{J} \in \mathcal{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$.</figcaption></figure>

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

$$3^{(n+g)/2} \cdot \left(\frac{2}{3}\right)^k. \qquad (12)$$

Nevertheless, we prove that an exact bound on the embedding number of Laman graphs can be derived considering a fixed edge, whose removal does not create multiple components. Recall from graph theory that given a connected graph $G = (V, E)$, a subset of vertices $S \subseteq V$ is called *vertex separator* if its removal breaks the connectivity.

**Lemma 17.** Let $G$ be a Laman graph, then $\exists e = (u, v) \in E(G)$ such that $G' = (G \setminus \{u\}) \setminus \{v\}$ is connected.

*Proof.* Since $G$ is a Laman graph, it is at least 2-connected [20]. If the minimum size separator contains at least 3 vertices, then the lemma is proven. In the other case, we denote a 2-vertex separator with $S_1$. If we remove $S_1$ from $G$, then we get two components $G_1, G'_1$.

If one of the two components, i.e. $G_1$, does not contain a separator, then $S_1$ is called *extreme*. This means that either $G[V(G_1)]$ contains edges, but the deletion of any 2 vertices does not break the connectivity, or there are no edges in $G[V(G_1)]$. In the latter case, every edge that is incident to a vertex in $G_1$, has its other endpoint in $S_1$. If $S_1$ is not an extreme separator, we repeat the process in $G_1$ without loss of generality, setting a new partition in $G_2, S_2, G'_2$ as before. We end the process when a separator in one of the two components is extreme.

Let us denote the two components and the separator in the end of this process with $G_S, G'_S$ and $S$ respectively. We consider $G_S$ to be the component with no separator. If there is an edge in one of the components, then trivially the deletion of its endpoints does not break the connectivity.

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

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

$$\frac{16}{3^{7/2}} \cdot (2 \cdot 3^{1/2})^{|V|-2}.$$

The asymptotic order of this bound is $O(3.46^{|V|})$.

*Proof.* In [4] it is proven that the bound of the embedding number for a Laman graph $G$ with a 2-valent vertex $v$ is the same with the number of orientations of the graph $G \setminus \{v\}$, so by Theorem 1 the number of orientations is
the same. This means that for the general bound, we may consider only Laman graphs with minimum degree 3. Since the number of hanging edges $k$ is equal to the number edges incident to the fixed vertices, but for the fixed vertex, we have that $k \ge 4$. Also, Lemma 17 indicates that there is always a fixed edge whose removal does not break connectivity.

By setting $k=4$ and $g=1$ in the upper bound on the 2-orientations given in Equation 16, and combining it with Theorem 1 we derive the new upper bound. □

# 4 Higher Dimensions

In this section we improve the bounds for all $d \ge 3$. The elimination method here is analogous with $d=2$. The main difference is that paths with multiple normal degree profiles shall be considered. Remark also that the case of Laman graphs is used as base case for some of our proofs. The asymptotic bound derived in this section is given by the following Theorem, that extends Theorem 18.

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

$$O\left( \left( 2 \cdot \binom{2d-1}{d}^{1/2} \right)^{|V|} \right).$$

Recall that $C_d(r, h)$ denotes the cost of the removal of a vertex with $r$ normal edges and $h$ hanging edges for $d$-pseudographs (Lemma 8). The following quantity

$$C_d(r, h)^{\frac{d-1}{r-1}} \qquad (13)$$

is the asymptotic effect for the elimination of a vertex with degree profile $(r, h)$, $r \ge 2$. The exponent in this quantity is not affected by the hanging degree of the vertices, so it is the same for all vertices with the same normal degree. We also consider that the asymptotic effect of vertices with normal degree 1 is trivially 1. Let us recall that there is no need to examine vertices such that $r+h < d$ or $h > d$, since they have no valid $d$-orientations [6].

The first step leading to the bound of $d$-orientations is to derive the maximal of the asymptotic effect for certain cases of degree profiles. More precisely we prove that the asymptotic effect of $(2d-1, 0)$ vertices is bigger or equal to the asymptotic effect of all other vertices examined in the following lemma. Thus, $C_d(2d-1, 0)^{\frac{1}{2}}$ shall be called target bound in the sequel.

**Lemma 20.** The asymptotic effect is maximized over all $1 \le r \le 2d-1$ with $0 \le h \le d$ for $(r, h) = (2d-1, 0)$, but for the cases $(r, h) = (2(d-h), h)$ with $1 \le h \le d-1$.

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

For the non-trivial cases, we first prove initially that $C_d(r, 0)^{\frac{d-1}{r-1}}$ is monotonically increasing for all integers in $r \in [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 \ge d$. Observe that the term $d-1$ is constant, so it suffices to prove that the ratio

$$U_d(r) = \frac{C_d(r+1, 0)^{r-1}}{C_d(r, 0)^r} = \left( \frac{\binom{r+1}{d}}{\binom{r}{d}} \right)^{r-1} \cdot \frac{1}{\binom{r}{d}} = \left( \frac{r+1}{r+1-d} \right)^{r-1} \cdot \frac{1}{\binom{r}{d}}$$

is bigger than 1 in this interval.

If we take the ratio $\frac{U_d(r+1)}{U_d(r)}$ we conclude that

$$\frac{U_d(r+1)}{U_d(r)} = \left( \frac{(r+2)(r+1-d)}{(r+1)(r+2-d)} \right)^r = \left( 1 - \frac{d}{(r+1)(r+2-d)} \right)^r$$

is always smaller than $1 \forall d \ge 2$, so $U_d(r)$ decreases and its minimum in $[d, 2d-1]$ is

$$U^*(d) = U_d(2d-1) = \frac{2^{2d-2}}{\binom{2d-1}{d}}.$$
For $d=2$ we have $U^*(d) = 4/3 > 1$ and it can be checked that $\frac{U^*(d+1)}{U^*(d)} = 1 + \frac{1}{2d+1}$, proving that $\forall d \ge 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 \in [d, 2d-1]$, concluding our claim.

The cases for $1 \le h \le d$ and $d-h \le r \le 2 \cdot (d-h) - 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 $d-h$ it also holds for these cases for $d$. We just proved that

$$C_{d-h}(r, 0)^{(d-h-1)/(r-1)} \le C_{d-h}(2(d-h)-1, 0)^{1/2}$$

holds in dimension $d-h$, with $d-h \ge 2$ (the base case for dimension 2 was proven in Section 3).

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

$$C_{d-h}(r, 0)^{(d-1)/(r-1)} \le 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)} \le C_d(2d-1, 0)^{1/2}. \quad (14)$$

This will be done by demonstrating that the ratio

$$\frac{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 \le h \le d$. In other words, the shift $h \to h+1$ reduces the asymptotic effect. Considering $d^* = d-h$, this shift turns to $d^* \to d^* - 1$ and the ratio becomes

$$W(d^*) = \frac{C_{d^*}(2d^*-1, 0)^{2d^*-4}}{C_{d^*}(2d^*-3, 1)^{2d^*-2}} = \left(\frac{4d^*-2}{d^*}\right)^{2d^*-4} \frac{1}{\left(\frac{2d^*-3}{d^*-1}\right)^2}$$

which is bigger than 1 for $d^* = 3$, since $10^2 > 3^4$.

Now the ratio

$$\frac{W(d^*)}{W(d^*-1)} = \left( \frac{(4d^*-2)(d^*-1)}{(4d^*-6)d^*} \right)^{2d^*-6} \cdot \left( \frac{\binom{2d^*-5}{d^*-2}}{\binom{2d^*-3}{d^*-1}} \cdot \frac{4d^*-2}{d^*} \right)^2 = \left( 1 + \frac{2}{4d^*^2 - 6d^*} \right)^{2d^*-4}$$

is also bigger than 1, showing that $W(d^*)$ is increasing.

What remains is to deal with the case of $(2(d-h), h^*)$ vertices with $h^* \ge h+1$, as well as the case of vertices with $r \ge 2(d-h)+1$ and more or equal than $h$ hanging edges. Notice that in the first case if the term $2(d-h)$ in

$$\binom{2(d-h)}{d-h^*},$$

if fixed, then this binomial coefficient decreases as $h^* \ge h$ increases. Since we have that $C_d(2(d-h), h+1) = C_d(2(d-h), h-1)$ and vertices $(2(d-h), h-1)$ have smaller asymptotic effect than $(2(d-h)+1, h-1)$ vertices as proven before, our hypothesis is valid.

The same comparison with $(2(d-h)+1, h-1)$ vertices can be done for $(2(d-h)+1, h^*)$ with $h^* \ge h$, since $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, we remark that in the previous 2 cases the cost function was maximized for vertices with $h$ hanging edges, from the properties of binomial coefficients. Thus, in examining the case $r \ge 2(d-h)+2$, we refer to the cases of vertices with fewer hanging edges that shall have higher cost. Our base case now is the $(2d-1, 1)$ and $(2d-1, 2)$ vertices. The first have asymptotic effect equal to the target bound, while the latter have strictly smaller effect. $\square$

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

$$\frac{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

inherited for vertices with the same normal degree and increased hanging degree in bigger dimensions. For instance,
in dimension 3, the vertices with higher asymptotic effect than the target bound are both the (4, 1) vertices and the (2, 2) vertices. The latter corresponds to the (2, 1) vertices in dimension 2, since they have the same cost.

We will treat these cases expanding the idea of grouping composite vertices presented in Section 3. Let us define the dichotomy between composite and non-composite vertices in general dimension. We recall that trivial vertices are the ones that have cost equal to 1.

**Definition 21.** Let $J$ be a pseudograph, in which we apply an elimination process to bound the number of its $d$-orientations. The non-composite vertices with normal degree $2(d-h)$, for $1 \le h \le d-1$ are the vertices with degree profile $(2(d-h), h)$, $(2(d-h), h+1)$, $(2(d-h), h-1)$ such that

* they had exactly this degree in $J$.

* they have this degree profile and they were generated by the removal of a trivial vertex with normal degree $r \le d$.

All the other vertices eliminated with this degree profile are called composite vertices with normal degree $2(d-h)$.

This definition serves to group all composite vertices for different path elimination steps. The non-composite vertices with degree profile $(2(d-h), h+1)$, $(2(d-h), h-1)$ have smaller asymptotic effect than the target bound, while the cardinality of non-composite $(2(d-h), h)$ vertices is bounded by the number of initial hanging edges, since they can be generated only by a drop in H.E.E.

Analogously with Lemma 14, there is always an elimination process such that no composite non-cut vertex can be generated by vertices with degree profile other than the ones belonging in the previous definition. The following lemma bounds the average cost for these vertices.

**Lemma 22.** *The removal of a composite path with normal degree $2(d-h)$ has eliminating average cost at most $D(d-h+1)$.*

*Proof.* First, we show that the cost function follows at worst case the recursion presented in Equation 6. We will first consider the case of a path $\mathcal{J}_d$ with a leading vertex $v_0$ that has normal degree $2d-1$, which can be generalized in all other cases. Let $\mathcal{B}_d(\ell)$ denote the number of pseudographs with a $(2d-2, 1)$ vertex to be eliminated and $\mathcal{G}_d(\ell)$ the number of pseudographs with a $(2d-2, 0)$ or a $(2d-2, 2)$ vertex or $(2d-2, 2)$ to be eliminated, when $\ell \ge 1$. Since vertex $v_0$ is eliminated with normal degree $2d-1$, it has cost $C_d(2d-1, 0) = \alpha_d + \beta_d$ in the worst case scenario. We also set $\mathcal{B}_d(0) = \mathcal{G}_d(0) = 1$ which satisfies the cost function and the count for the distribution of hanging edges (Lemma 9). By Lemma 9, eliminating a $(2d-2, 1)$ vertex gives a hanging edge to one of its neighbours in exactly $(2d-3)$ ways, while in the rest $(2d-3)$ ways this neighbour does not acquire any hanging edge. Both quantities are equal to $\alpha_d/2$. Similarly in the cases of $(2d-2, 2)$ vertices, a neighbour acquires a hanging edge in $\beta_d - \alpha_d/2$ cases and does not get any in $\alpha_d/2$ cases, while for $(2d-2, 2)$ vertices this counts are reversed. This means that the worst case scenario follows Equation 4 for $\mathcal{B}_d$ and $\mathcal{G}_d$, if we substitute $\mathcal{B}_d$ with $\mathcal{B}_d$ and $\mathcal{G}_d$ with $\mathcal{G}_d$. Therefore, the cost function $C_d$ follows at the worst case scenario the recursive Equation 6 substituting $C_d$ with $C_d$. This gives the upper bound $\mathcal{D}(d)$ for the average cost if the first vertex is eliminated as a vertex with degree profile $(2d-1, 0)$. If the first vertex has normal degree $(2d-1, h)$ with $h \ge 2$, we can make a similar modification as with $(3, 2)$ vertices in the case of Laman graphs (see Lemma 15) and use the eliminating average cost for the paths.

The case of the removal of a single path with leading vertex that has normal degree $2d-1$ is proven, but Definition 21 and the adjustment of Lemma 14 in dimensions $d \ge 3$ allow the generation of composite vertices in $\mathcal{J}_{d-h}$ with $h \ge 1$, after the removal of another path $\mathcal{J}_d$ or a single vertex $u$ with normal degree $2d-1$. Now we consider that the leading vertex of $\mathcal{J}_{d'}$ is either the last vertex of $\mathcal{J}_d$, or the single vertex $u$. So it remains to prove that the removal of all vertices in both paths does not violate the eliminating average cost.

Let us consider the case of eliminating a $\mathcal{J}_d$ path, or a vertex $u$ with normal degree $2d-1$, followed by the elimination of a $\mathcal{J}_{d'}$ path, with $d > d'$. In both cases the leading vertex $v_0$ of $\mathcal{J}_{d'}$ is considered to be either the last vertex of $\mathcal{J}_d$ or $u$. If the removal of both $\mathcal{J}_d$ and $\mathcal{J}_{d'}$ increased the connected components, the elimination would not be valid. Thus, we are allowed to remove the paths in any order.

The cost for elimination of the first path $\mathcal{J}_d$ follows the count set above. Let now $\mathcal{B}_{d'}(0), \mathcal{G}_{d'}(0)$ denote number of pseudographs with vertices that have normal degree $2d-2$ in the final step of the $\mathcal{J}_d$ removal, otherwise in the case of a single vertex we have $\mathcal{B}_{d'}(0) = \mathcal{G}_{d'}(0) = 1$. If we have the elimination of $\mathcal{J}_d$, we can always consider the worst case scenario, which means that $\mathcal{B}_d, \mathcal{G}_d, C_d$ follow the recursive functions $\mathcal{B}_d, \mathcal{G}_d, C_d$ in Lemma 11. This modification is in accordance with the definition of the effective cost and the eliminating average cost, so it does not affect the derivation of the general upper bound. In the worst case scenario we have always $\mathcal{B}_{d'}(0) \le \mathcal{G}_{d'}(0)$, with the equality holding only in the case of single vertex. $\mathcal{B}_{d'}(1)$ and $\mathcal{G}_{d'}(1)$ denote number of pseudographs with vertices that have normal degree $2d' - 2$ in the next step of elimination of $\mathcal{J}_{d'}$, with the cost of the first ones being $\alpha_{d'}$ and the second
ones being $\beta_{d'}$. We also denote the cost of the paths $C_{d'}(0)$ and $C_{d'}(1)$ respectively. Now, the worst case scenario for the cost $C_{d'}$, would be to consider $B_{d'}(1) = \frac{\alpha_d}{2}(B_{d'}(0) + G_{d'}(0))$ and $G_{d'}(1) = \frac{\alpha_d}{2}B_{d'}(0) + (\beta_d - \frac{\alpha_d}{2})G_{d'}(0)$.

Now we prove that

$$ \frac{C_{d'}(1)}{C_{d'}(0)} \le \frac{\alpha_{d'}^2 + \beta_{d'}^2}{\alpha_{d'} + \beta_{d'}} \qquad (15) $$

for all the cases in which the total cost of $\mathcal{J}_d$ follows the worst case scenario.

We have that

$$ \begin{aligned} \frac{C_{d'}(1)}{C_{d'}(0)} &= \frac{\alpha_{d'} B_{d'}(1) + \beta_{d'} G_{d'}(1)}{\alpha_{d'} B_{d'}(0) + \beta_{d'} G_{d'}(0)} \\ &= \frac{\alpha_{d'} (\alpha_d \cdot B_{d'}(0)/2 + \alpha_d \cdot G_{d'}(0)/2) + \beta_{d'} (\alpha_d \cdot B_{d'}(0)/2 + \beta_d G_{d'}(0) - \alpha_d \cdot G_{d'}(0)/2)}{\alpha_d B_{d'}(0) + \beta_d G_{d'}(0)} \\ &= \frac{\alpha_{d'} (C_{d'}(0)/2 - \beta_d \cdot G_{d'}(0)/2 + \alpha_d \cdot G_{d'}(0)/2) + \beta_{d'} (C_{d'}(0)/2 - \alpha_d \cdot G_{d'}(0)/2 + \beta_d \cdot G_{d'}(0)/2)}{\alpha_d B_{d'}(0) + \beta_d G_{d'}(0)} \\ &= \frac{\alpha_{d'} + \beta_{d'}}{2} + \frac{(\alpha_{d'} - \beta_{d'}) \cdot (\alpha_d - \beta_d) G_{d'}(0)}{2(\alpha_d B_{d'}(0) + \beta_d G_{d'}(0))} \end{aligned} $$

Since

$$ \frac{\alpha_{d'}^2 + \beta_{d'}^2}{\alpha_{d'} + \beta_{d'}} - \frac{\alpha_{d'} + \beta_{d'}}{2} = \frac{(\alpha_{d'} - \beta_{d'})^2}{2 \cdot (\alpha_{d'} + \beta_{d'})} $$

and $\alpha_{d'} > \beta_{d'}$, Inequality 15 is satisfied if

$$ \frac{(\alpha_d - \beta_d) \cdot G_{d'}(0)}{\alpha_d B_{d'}(0) + \beta_d G_{d'}(0)} \le \frac{\alpha_{d'} - \beta_{d'}}{\alpha_{d'} + \beta_{d'}}. $$

The relation $(d-1) \cdot \alpha_d = d \cdot \beta_d$, holds for every $d \ge 2$, so the inequality becomes

$$ \frac{G_{d'}(0)}{d \cdot B_{d'}(0) + (d-1) \cdot G_{d'}(0)} \le \frac{1}{2d' - 1} \Leftrightarrow (2d' - d) \cdot G_{d'}(0) \le d \cdot B_{d'}(0). $$

Since $2d' - d < d$ and $G_{d'}(0) \le B_{d'}(0)$ the inequality is proven.

It remains to show $C_{d'}(\ell+1)/C_{d'}(\ell) \le \frac{\alpha_{d'}^2 + \beta_{d'}^2}{\alpha_{d'} + \beta_{d'}}$, for $\ell \ge 1$. The sequence follows at the worst case the recursion established in Lemma 11, so we may use the inequalities established in the proof of Lemma 12 to prove the cases of $C_{d'}(\ell+1)/C_{d'}(\ell)$ with $\ell \ge 1$. For $\ell \ge 4$ there is nothing to prove since the inequality $(\alpha_{d'} - 2\beta_{d'}) \cdot C_{d'}(\ell-3) \le \alpha_{d'}(\alpha_{d'} - \beta_{d'}) \cdot C_{d'}(\ell-4)$ always holds as explained in Lemma 12. The case $C_{d'}(3)/C_{d'}(2)$ is proved as equivalent to $C_{d'}(1)/C_{d'}(0) \le \alpha_{d'}$, which holds, since $C_{d'}(1)/C_{d'}(0) \le (\alpha_{d'}^2 + \beta_{d'}^2)/((\alpha_{d'} + \beta_{d'}) \le \alpha_{d'}$. Now for the last two cases, we can consider the inequalities established for $C_{d'}(2)/C_{d'}(1)$ and $C_{d'}(4)/C_{d'}(3)$ in Lemma 12, which are always true if we consider $C_{d'}(1)/C_{d'}(0) = (\alpha_{d'}^2 + \beta_{d'}^2)/((\alpha_{d'} + \beta_{d'}))$. $\square$

**Lemma 23.** The asymptotic effect for the eliminating average cost of paths $\mathcal{J}_{d-h+1}$ is always smaller than the asymptotic effect of $(2d-1, 0)$ vertices in the case of $d$-orientations.

*Proof.* The asymptotic effect in the case of paths is $\mathcal{D}(d-h+1)^{\frac{d-1}{2(d-h)-1}}$. First we prove that this holds for $h=1$. Recall that $\alpha_d/\beta_d = d/(d-1)$.
$$ 
\begin{aligned}
& \frac{\mathcal{D}(d)^{2d-2}}{C_d(2d-1, 0)^{2d-3}} < 1 \iff \\
& \frac{(\alpha_d^2 + \beta_d^2)^{2d-2}}{(\alpha_d + \beta_d)^{4d-5}} < 1 \iff \\
& \left( \frac{\alpha_d^2 + \beta_d^2}{(\alpha_d + \beta_d)^2} \right)^{2d-2} \cdot (\alpha_d + \beta_d) < 1 \iff \\
& \left( 1 - \frac{2\alpha_d\beta_d}{(\alpha_d + \beta_d)^2} \right)^{2d-2} \cdot (\alpha_d + \beta_d) < 1 \iff \\
& \left( 1 - \frac{2d \cdot (d-1)}{(2d-1)^2} \right)^{2d-2} \cdot \begin{pmatrix} 2d-1 \\ d \end{pmatrix} < 1 \iff \\
& \left( \frac{2d^2 - 2d + 1}{(2d-1)^2} \right)^{2d-2} \cdot \begin{pmatrix} 2d-1 \\ d \end{pmatrix} < 1
\end{aligned}
$$

which holds for $d = 2$. So we need to show that the following function is monotonically decreasing for $d \ge 2$.

$$ A(d) = \left( \frac{2d^2 - 2d + 1}{(2d-1)^2} \right)^{2d-2} \cdot \begin{pmatrix} 2d-1 \\ d \end{pmatrix} $$

We have that

$$ 
\begin{aligned}
\frac{A(d+1)}{A(d)} &= \frac{\left( \frac{2(d+1)^2 - 2(d+1) + 1}{(2d+1)^2} \right)^{2d} \cdot \begin{pmatrix} 2d+1 \\ d+1 \end{pmatrix}}{\left( \frac{2d^2 - 2d + 1}{(2d-1)^2} \right)^{2d-2} \cdot \begin{pmatrix} 2d-1 \\ d \end{pmatrix}} \\
&= \frac{\left( \frac{2(d+1)^2 - 2(d+1) + 1}{(2d+1)^2} \right)^{2d} \cdot 2(2d+1)}{\left( \frac{2d^2 - 2d + 1}{(2d-1)^2} \right)^{2d-2} \cdot (d+1)} \\
&= \left( \frac{(2d-1)^2 \cdot (2(d+1)^2 - 2(d+1) + 1)}{(2d+1)^2 \cdot (2d^2 - 2d + 1)} \right)^{2d-2} \cdot \frac{2 \cdot (2(d+1)^2 - 2(d+1) + 1)^2}{(2d+1)^3 \cdot (d+1)} \\
&= \left( \frac{8d^4 - 2d^2 - 2d + 1}{8d^4 - 2d^2 + 2d + 1} \right)^{2d-2} \cdot \frac{8d^4 + 16d^3 + 16d^2 + 8d + 2}{8d^4 + 20d^3 + 18d^2 + 7d + 1}.
\end{aligned}
$$

Both fractions are less than 1 for all $d \ge 1$.

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

$$ \mathcal{D}(d-h+1)^{\frac{d-h-1}{2(d-h)+1}} \le C_{d-h+1}(2(d-h+1)-1,0)^{1/2} \quad (16) $$

for $h \ge 2$. This means that $\mathcal{D}(d-h+1)^{\frac{d-1}{2(d-h)+1}}$ is bounded using similar inequalities as in Equation 14 from Lemma 20. $\square$

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

**Lemma 24.** The following ratio is bigger than 1 for $1 \le h \le d-2$.

$$ \frac{2^{2(d-h)-1}}{C_d(2(d-h), h)} $$

*Proof.* Let us denote $d^* = d-h$ as in Lemma 20 and by $S(d^*)$ the above ratio. Since the shift $d^* \to d^*+1$ corresponds to the shift $h \to h-1$. Taking the ratio

$$ \frac{S(d^*+1)}{S(d^*)} = 1 + \frac{1}{2d^*+1}, $$

one deduces that $S(d^*)$ is clearly increasing. Since $S(2) = 8/6$, the condition holds. $\square$
Now we are ready to prove the bound on d-orientations.

**Theorem 25.** The number of d-orientations for a connected d-pseudograph with n vertices and k hanging edges is bounded by

$$ \left( \binom{2d-1}{d} \right)^{\frac{n+\frac{1}{d-1}}{2}} \cdot \left( \frac{2}{\binom{2d-1}{d}^{\frac{1}{d-1}}} \right)^k \quad (17) $$

*Proof.* Let us list the basic categories of vertices to be eliminated and provide a notation for their cardinalities during the elimination process.

* $t_d$ vertices with normal degree $2d-1$. For these vertices we consider the maximum cost $C_d(2d-1, 0)$.

* $s_r$ vertices with degree profile $(r, h)$, such that their asymptotic effect is strictly smaller than the target bound. For these vertices, we consider the effective cost of their elimination omitting $h$ from the cost function: $C_d^*(r) = \max_{\substack{0 \le h \le d \\ h \ne (r-2d)/2}} C_d(r, h)$.

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

* $\ell_h$ vertices with normal degree $2(d-h)$, for $1 \le h \le d-1$ eliminated with path elimination step.

* $m_h$ vertices with degree profile $(2(d-h), h)$, such that their asymptotic effect is bigger than the target bound.

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

The total cost of the elimination process is bounded by

$$ C_d(2d-1, 0)^{td} \cdot \prod C_d^*(r)^{s_r} \cdot \prod D(d-h+1)^{\ell_h} \cdot \prod C_d(2(d-h), h)^{m_h} \quad (18) $$

By Lemma 5, the elimination process stops when tree condition $(d-1) \cdot 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 - \sum s_r - \sum \ell_h - \sum m_h $$

$$ k' = k + (d-1) \cdot t_d + \sum (r-d) \cdot s_r - \sum (d-2h) \cdot \ell_h - \sum (r-d) \cdot 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 \le \frac{n}{2} - \frac{1 + k - \sum (r-1) \cdot s_r - \sum (2(d-h)-1) \cdot \ell_h - \sum (r-1) \cdot m_h}{2d-2} $$

Applying this inequality to Equation 18, it is deduced that the following quantity bounds the number of orientations

$$ C_d(2d-1, 0)^{\frac{n}{2} - \frac{k-1}{2d-2}} \cdot \prod \left( \frac{C_d^*(r)}{C(2d-1, 0)^{\frac{r-1}{2d-2}}} \right)^{s_r} \cdot \prod \left( \frac{D(d-h+1)}{C(2d-1, 0)^{\frac{2(d-h)-1}{2d-2}}} \right)^{\ell_h} \cdot \prod \left( \frac{C_d(2(d-h), h)}{C(2d-1, 0)^{\frac{2(d-h)-1}{2d-2}}} \right)^{m_h} $$

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 (see Lemmata 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

$$ C(2d-1, 0)^{\frac{n}{2} - \frac{k-1}{2d-2}} \left( \frac{2}{C(2d-1, 0)^{\frac{1}{2d-2}}} \right)^{\sum m_h} $$

By the definition of non-composite vertices with asymptotic effect bigger than the target bound, we have that $\sum m_h$ is bounded by the initial number of hanging edges $k$. Thus, the bound in Equation 17 follows. □

**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 its removal does not break the connectivity of G.
Proof. The graph $G$ is at least $d$-connected. Let $S$ be the minimum separator of $G$. Note that $|S| \ge d$. Hence the removal of any subgraph of $G$ with less than $d$ vertices cannot break its connectivity. □

Now we are ready to prove Theorem 19.

Proof (Theorem 19). First we prove that $\frac{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

$$ \frac{2^d \cdot \binom{2d-1}{d}}{2^{d-1} \cdot \binom{2^{d+1}}{d+1}} = \frac{d+1}{2d+1} < 1 $$

for all $d \ge 2$. This implies that $2^{d-1} < C(2d-1,0)$ holds for every $d \ge 2$, since for $d=2$ we have that $2 < \binom{3}{2}$.

Lemma 26 indicates that there is always at least a fixed $K_2$ that is not a separator for $d \ge 3$. The bound results applying Theorem 25 for $d$-orientations to Theorem 1. □

<table><caption>Table 1: The base to the power of $|V|$ for the asymptotic bound in dimensions $2 \le d \le 9$. Bézout denotes the Bézout bound, BES is the bound derived in [4] using matrix permanents, BEV is the bound derived in [6] using elimination to bound outdegree-constrained orientations, and new is derived in this paper.</caption><thead><tr><th>d =</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th></tr></thead><tbody><tr><td>Bézout</td><td>4</td><td>8</td><td>16</td><td>32</td><td>64</td><td>128</td><td>256</td><td>512</td></tr><tr><td>BES</td><td>4.89</td><td>8.94</td><td>16.7</td><td>31.7</td><td>60.7</td><td>117.1</td><td>226.8</td><td>441</td></tr><tr><td>BEV</td><td>3.78</td><td>6.84</td><td>12.68</td><td>23.89</td><td>45.53</td><td>87.46</td><td>168.9</td><td>327.4</td></tr><tr><td>new</td><td>3.46</td><td>6.32</td><td>11.83</td><td>22.44</td><td>42.98</td><td>82.84</td><td>160.4</td><td>311.8</td></tr></tbody></table>

# 5 Lower bounds on the maximal number of $mBe$.

In the previous sections, we improve the upper bound for the embedding number of minimally rigid graphs. Despite this improvement, still the gap between the new upper bounds and lower bounds in the bibliography remain: in the case of Laman graph embeddings in $\mathbb{C}^2$ the asymptotic order of the new upper bound is $O(3.4641^{|V|})$, while there have been reported graphs with at most $\Omega(2.3780^{|V|})$ complex embeddings. Besides computing graphs with big number of embeddings and establishing new lower bounds (which requires big computational resources and has been the subject of a whole publication [13]), we are also interested in the tightness of our results with respect to the $mBe$ and the number of outdegree-constrained orientations. Recall, that the bounds of Theorem 18 and Theorem 19, are actually bounds on the m-Bézout bound of algebraic systems (as explained in [4]) and use bounds on orientations that we establish in Theorem 16 and Theorem 25.

Thus, in this section we provide examples of Laman graphs with maximal number of 2-orientations, among certain cases we computed, and we compare them with the bound on the embeddings given in Theorem 18 and the bound on the orientations given in Theorem 16. Let us remark that an exhaustive search over all Laman graphs with big number of vertices is almost infeasible, since their number is gigantic. For that reason, graphs were constructed by using repetitive Henneberg steps [20] to Laman graphs with big embedding number (data for the embedding numbers was found in [13]). To provide these bounds, we calculate them using the code from [7].

Given a Laman graph $G(V, E)$, we denote with $\mu(G)$ the number of its complex embeddings. Recall that $mBe(G, e)$ denotes the bound derived from Theorem 1 for a fixed edge $e = (u, v) \in E$ and $\mathcal{R}(G, e)$ the corresponding number of orientations.

Then applying Theorem 18, the following inequality holds:

$$ \mu(G) \le \min_{e \in E}(mBe(G, e)) \le mBe(G, e) \le \frac{16}{3^{7/2}} \cdot (2 \cdot 3^{1/2})^{|V|-2} \quad (19) $$

since the bound can vary for different fixed edges. In the case of Theorem 16 we have the following inequality:

$$ \mathcal{R}(G, e) \le 3^{n/2} \cdot (2/3)^k \cdot 3^{1/2}, \quad (20) $$
where $n$ denotes the number of vertices of the 2-pseudograph and $k$ the number of its hanging edges. Recall, that given a Laman graph $G(V, E)$ and a fixed edge $e$, the number of vertices for 2-pseudograph $J$ resulting from the deletion of $e$ is exactly $n = |V| - 2$.

We compare the asymptotic order of our bounds in the number of vertices with actual results of the mBe and the orientations, that are $O(3.4641^{|V|})$ and $O(1.7320^n)$ respectively. In order to compute the asymptotic order of the bound on the embeddings, we consider the number of non-fixed vertices in the exponent as in [3, 13]. This choice is made due to the underlying algebraic systems that lead to the bound in [4]. We also factor out the constant term $\frac{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 $n$, i.e. $3^{1/2} \cdot (2/3)^k$, to derive the exponential order only in $n$. Notice, that this number varies up to the number of hanging edges. Given a fixed edge $e = (u, v)$, the number of hanging edges for the resulting pseudograph is exactly $k = \text{deg}(u) + \text{deg}(v) - 2$, where $\text{deg}(\cdot)$ denotes the degree of a vertex.

<figure><img src="image_8.png" /><figcaption>Figure 7: The graph $G_{29a}$ is a Laman graph on 29 vertices. The dashed blue edge corresponds to the fixed edge that yields the maximal mBe. Note that $k = 6$ for the specific fixed edge.</figcaption></figure>

Let us present two examples of Laman graphs with large m-Bézout number.

The graph $G_{29a}$ is a 29-vertex graph and has the maximum asymptotic bound we have computed (see Figure 7). For the edge $e$ that maximizes this bound, we have that $mBe(G_{29a}, e) = 21,947,282,882,560$, so $R(G_{29a}, e) = 163,520$. Now, in order to find the asymptotic order of the number for mBe we compute $(\frac{3^{7/2}}{16} \cdot mBe(G_{29a}, e))^{1/27} = 3.2462$. In the case of orientations, notice that both fixed vertices have degree 4, so $k = 6$. Then we compute $(3^{-1/2} \cdot (\frac{3}{2})^6 \cdot R(G_{29a}, e))^{1/27} = 1.6726$. Thus, here we show that there are minimally rigid graphs with $\Omega(3.2462^{|V|})$ as m-Bézout number and 2-pseudographs with $\Omega(1.6726^n)$ orientations. We believe that with bigger computational resources, these numbers can be further increased.

Although this graph has a big bound for this specific edge, $\min_{e' \in E}(mBe(G_{29a}, e'))$ is much lower, namely 416, 611, 827, 712 with an asymptotic order of 2.8029, while for the actual number of embeddings we get only $\mu(G_{29a}) = 1, 624, 244, 224^4$.

Besides the maximal mBe, we ran also computations to find graphs with big minimum mBe (see Equation 19). The graph that has the maximum minimal m-Bézout number, among the ones we computed, is $G_{29b}$ (see Figure 8). For the edge $e'$ that minimizes the bound for the specific graph, we have that $mBe(G_{29b}, e') = 784,502,620,160$, which yields $(\frac{3^{7/2}}{16} \cdot mBe(G_{29b}, e'))^{1/27} = 2.8694$ as an asymptotic order. The number of hanging edges for the resulting pseudograph is $k = 5$, that gives $(3^{-1/2} \cdot (\frac{3}{2})^5 \cdot R(G_{29b}, e))^{1/27} = 1.4564$ as an asymptotic order $^5$.

<footnote n="4">⁴We thank Georg Grasegger for this computation</footnote>

<footnote n="5">⁵Let us note that Georg Grasseger informed us that their algorithm could not compute the embedding number for this graph.</footnote>
<figure><img src="image_9.png" /><figcaption>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$.</figcaption></figure>

# 6 Conclusions and future work

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

More demanding computations are also required for improving the lower bounds on the embedding number that may reduce the gap between lower and upper bounds. In the case that the bound is indeed sharp on orientations, but loose for the embedding number, one may consider other ways to improve upper bounds. One idea is to examine if there are certain combinatorial properties for the fixed $K_d$ whose removal minimizes the number of orientations. Another approach would be to consider tools from sparse algebraic geometry on determinantal varieties of Cayley-Menger matrices.

Finally, our bounds may be extended generally for all outdegree-constrained *d*-orientations. In that case the restriction on degree is not applied for (2d − 1)-valent vertices, but for (2d)-valent vertices. This result may also have applications on the multihomogeneous bound of certain polynomial systems, as demonstrated in [5].

**Acknowledgements** EB was fully supported and IZE was partially supported by project ARCADES which has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 675789. EB and IZE are members of team AROMATH, joint between INRIA Sophia-Antipolis, France, and NKUA, Greece.

# References

[1] L. Asimow and B. Roth. The rigidity of graphs. *Trans. American Mathematical Society*, 245:279-289, 1978.

[2] J. Baglivo and J. Graver. *Incidence and Symmetry in Design and Architecture*. Number 7 in Cambridge Urban and Architectural Studies. Cambridge University Press, 1983.

[3] E. Bartzos, I.Z. Emiris, J. Legerský, and E. Tsigaridas. On the maximal number of real embeddings of minimally rigid graphs in $R^2$, $R^3$ and $S^2$. *J. Symbolic Computation*, 102:189-208, 2021.

[4] E. Bartzos, I.Z. Emiris, and J. Schicho. On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs. *J. Applicable Algebra in Engineering, Communication & Computing*, 31(5):325-357, 2020.
[5] E. Bartzos, I.Z. Emiris, and C. Tzamos. The m-Bézout bound and distance geometry. In F. Boulier, M. England, T.M. Sadykov, and E.V. Vorozhtsov, editors, *Proc. Computer Algebra in Scientific Computing - 23rd Intern. Workshop, CASC, Sochi, Russia*, volume 12865 of LNCS, pages 6–20. Springer, 2021.

[6] E. Bartzos, I.Z. Emiris, and R. Vidunas. New upper bounds for the number of embeddings of minimally rigid graphs. *Discrete & Computational Geometry*, 68(3):796–816, 3 2022.

[7] E. Bartzos and J. Schicho. Source code and examples for the paper "On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs", November 2019. https://doi.org/10.5281/zenodo.3542061.

[8] L.M. Blumenthal. *Theory and Applications of Distance Geometry*. Chelsea Publishing, New York, 1970.

[9] C. Borcea and I. Streinu. The number of embeddings of minimally rigid graphs. *Discrete & Computational Geometry*, 31(2):287–303, 2004.

[10] J. Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, and J. Schicho. The number of realizations of a Laman graph. *SIAM J. Applied Algebra & Geometry*, 2(1):94–125, 2018.

[11] D.G. Emmerich. *Structures Tendues et Autotendantes*. Ecole d'Architecture de Paris, La Villette, France, 1988.

[12] M. Gallet, G Grasegger, and J Schicho. Counting realizations of Laman graphs on the sphere. *Electron. J. Comb.*, 27(2), 2020.

[13] G Grasegger, C Koutschan, and E Tsigaridas. Lower bounds on the number of realizations of rigid graphs. *Experimental Mathematics*, 29(2):1–12, 2017.

[14] F. Harary. *Graph Theory*. Addison-Wesley, 1969.

[15] J. Harris and L.W. Tu. On symmetric and skew-symmetric determinantal varieties. *Topology*, 23:71–84, 1984.

[16] G. Laman. On graphs and rigidity of plane skeletal structures. *J. Engineering Math.*, 4(4):331–340, 1970.

[17] C. Lavor, L. Liberti, B. Donald, B. Worley, B. Bardiaux, T.E. Malliavin, and M. Nilges. Minimal NMR distance information for rigidity of protein graphs. *Discrete Applied Mathematics*, 256:91–104, 2019. Spec. Issue on Distance Geometry Theory & Applications’16.

[18] J.C. Maxwell. On the calculation of the equilibrium and stiffness of frames. *Philosophical Magazine*, page 39(12), 1864.

[19] H. Pollaczek-Geiringer. Über die Gliederung ebener Fachwerke. *Zeitschrift für Angewandte Mathematik und Mechanik (ZAMM)*, 7(1):58–72, 1927.

[20] B. Schulze and W. Whiteley. Rigidity and scene analysis. In J.E. Goodman, J. O'Rourke, and C.D. Tóth, editors, *Handbook Discrete & Computational Geom.*, chapter 61, pages 1593–1632. CRC Press, 2017.

[21] W. Whiteley. Cones, infinity and one-story buildings. *Topologie Structurale*, 8:53–70, 1983.

[22] D. Zelazo, A. Franchi, F. Allgöwer, H. H. Bülthoff, and P.R. Giordano. Rigidity maintenance control for multi-robot systems. In *Proc. Robotics: Science & Systems*, Sydney, Australia, 2012.