2D Minimal Graph Rigidity is in $\mathrm{𝖭𝖢}$ for One-Crossing-Minor-Free Graphs

A bar-and-joint framework can be seen as a graph $G$, where vertices are the joints and edges are the bars, together with an embedding $p:V\to {ℝ}^2$, for the case of $2$D. The vertices of $G$ are allowed to move continuously subject to the constraint that the distance between adjacent vertices does not change, i.e., the lengths of the bars are fixed. A framework $(G,p)$ is rigid if every such continuous motion of the framework preserves the distance of all pairs of vertices, i.e., also of non-adjacent vertices. Otherwise the framework is flexible.

A natural question is whether rigidity/flexibility is just the property of the underlying graph $G$ or whether it also depends on the specific embedding $p$. That is, whether rigidity is just determined by the combinatorial structure of the bars, i.e. which tuples of bars are connected at one joint, and does not depend on the specific lengths of the bars. The first answer is that there are examples that show that rigidity depends on the embedding $p$. However, for any graph, either almost all of its embeddings are rigid or almost all of them are flexible [16, 5]. Therefore one defines a graph $G$ to be rigid if almost all embeddings $p$ result in a rigid framework $(G,p)$, otherwise $G$ is flexible. Graph rigidity can be equivalently defined based on the notion of infinitesimal rigidity, see Section 2.1 and Definition 4.

A graph is minimally rigid if the removal of any edge makes it flexible. Minimally rigid graphs have a combinatorial characterization that is often attributed to Laman, but was already known to Geiringer.

The Laman condition (2) gives rise to a matroid, the rigidity matroid for a graph $G=(V,E)$. The ground set is the set of edges $E$. A set $E^{\prime }\subseteq E$ is independent, if graph $(V,E^{\prime })$ fulfills (2). The base sets of this matroid are the minimally rigid subgraphs of $G$ (on $V$).

There is another combinatorial characterization.

There is also an iterative way to construct Laman graphs, known as the Henneberg construction [21], where we start with an edge, and then add a node to the graph constructed so far in one of two ways (Theorem 13). This is explained in more detail in Section 2.4.

In $2$D, rigidity can be solved in polynomial time, namely in time $𝒪(n^2)$ [20, 15]. For minimal rigidity, this has been improved to $𝒪(n\sqrt{n\log n}+m)$ [15]. We are interested in the parallel complexity of minimal rigidity.

Note that the characterization of minimal rigidity in Theorem 2 is similar in nature to Hall’s Theorem [19] that characterizes the existence of perfect matchings in bipartite graphs. This can actually be formalized to a reduction from the minimal rigidity problem to the bipartite perfect matching problem [20]. Since the reduction to bipartite perfect matching is efficient in parallel, i.e. in $\mathrm{𝖭𝖢}$, the parallel complexity of bipartite perfect matching carries over to minimal rigidity. Bipartite perfect matching is in randomized $\mathrm{𝖭𝖢}$, $\mathrm{𝖱𝖭𝖢}$ [33]. The derandomization question, whether one can avoid the randomness without much loss in efficiency, is of major interest in complexity theory. A few years back, the randomized algorithm has been derandomized to a quasi-$\mathrm{𝖭𝖢}$ bound for bipartite perfect matching [14]. This result implies a quasi-$\mathrm{𝖭𝖢}$ algorithm for minimal rigidity. One of the major motivations for us to study minimal graph rigidity is that we might have better chances to show that it is in $\mathrm{𝖭𝖢}$ than for bipartite perfect matching. That is, minimal rigidity is the litmus test for bipartite perfect matching. Note that a reduction in the other direction is not known. Hence, minimal rigidity might be easier than bipartite perfect matching.

Interestingly, also the complexity questions around general rigidity (i.e., not necessarily minimal), have a status quite similar to those around the bipartite matching problem. Using the matroid property, one can get a polynomial-time algorithm to test if a graph is rigid. Both problems, matching and rigidity, reduce to the polynomial identity testing (PIT) problem [33, 35], and thus they have $\mathrm{𝖱𝖭𝖢}$-algorithms. Its connection with matching and PIT makes graph rigidity a very interesting candidate for studying derandomization.

First, we observe that for planar graphs one can decide minimal rigidity and compute an infinitesimally rigid realization in ${\mathrm{𝖭𝖢}}^2$ (Theorem 19). This is based on results in [40, 18, 38]

Our first main result is that for $K_{3,3}$-free graphs, we can decide whether a graph is Laman in ${\mathrm{𝖭𝖢}}^2$ (Theorem 23) and also compute a rigid realization (Theorem 25).

Also whether a one-crossing-minor-free graph is Laman can be decided in ${\mathrm{𝖭𝖢}}^3$ (Theorem 29). However, an $\mathrm{𝖭𝖢}$-algorithm for computing a rigid realization for one-crossing-minor-free graphs or bounded treewidth graphs remains an open problem.

Note that extending results from planar graphs to such minor-free graphs is a technically nontrivial step that has also been done in other contexts, for example, famously by Vazirani [43]: Kasteleyn [24] showed that the number of perfect matchings in planar graphs can be efficiently computed. Then, based on a result of Little [28], Vazirani [43] extended the result to $K_{3,3}$-free graphs in ${\mathrm{𝖭𝖢}}^2$. Later, the result was further extended to $K_5$-free graphs in ${\mathrm{𝖭𝖢}}^3$ [39]. There are many more results in a similar flavor, see for example [10, 42, 26, 25, 3, 8, 7, 12]. Although the literature gives a meta strategy, a result for planar graphs does not automatically imply a result for other minor-free graph classes and new ideas are required.

Following the literature, we decompose the given one-crossing-minor-free graph (or $K_{3,3}$-free graph) into planar components or components of bounded treewidth. We observe that there are parallel algorithms to decide rigidity of graphs of bounded treewidth, see Section 2.2. Hence, for planar and bounded treewidth components we can check whether they are Laman. Our main technical tools which allow us to lift the results from planar/bounded treewidth case to $K_{3,3}$-free/one-crossing-minor free graphs are as follows.

• $\mathrm{■}$

  Characterization of Laman graphs in terms of Lamanness of certain split graphs obtained by splitting the graph along separating pairs/triples (Lemmas 22, 26).

• $\mathrm{■}$

  For all families of $3$-vertex graphs, we construct gadget graphs such that adding the gadget to a graph makes it Laman if and only if adding some member of the family makes it Laman (Lemma 28).

• $\mathrm{■}$

  Combining rigid embeddings of a set of Laman graphs to find a rigid embedding of a Laman graph obtained by joining them using $2$-sum operations (Lemma 24).

Note that obtaining a parallel algorithm for minimal rigidity does not give the same for rigidity, as there is no parallel reduction known. In fact, finding an $\mathrm{𝖭𝖢}$ (or quasi-$\mathrm{𝖭𝖢}$) algorithm for $2$D graph rigidity is open, even for planar graphs.

Let $G$ be Laman. By Lemma 15, there is a Henneberg construction for $G$ that starts with edge $(u,v)$. Recall that this is independent of whether $(u,v)$ is an edge in $G$. When a new vertex is added in the Henneberg sequence, it belongs to exactly one of the split graphs $G_i$ and the extension cannot interfere with some vertex from another split graph. Otherwise, the separating pair would not separate the split graphs from each other in $G$.

1. 1.

   If $(u,v)\in E$, this gives us Henneberg sequences for all split graphs by subdividing the sequence for $G$ in its parts for $G_1,\mathrm{\dots },G_{\mathrm{\ell }}$, respectively. Hence, they are all Laman.

2. 2.

   If $(u,v)\notin E$, it has been replaced by a type $2$ extension adding a vertex in exactly one split graph, say $G_1$. Again we subdivide the Henneberg sequence for $G$, and get sequences for $G_1$ and for $G_2+(u,v),\mathrm{\dots },G_{\mathrm{\ell }}+(u,v)$. Therefore, they are all Laman.

For the backward direction, in the first case, we consider Henneberg constructions for $G_1,G_2,\mathrm{\dots },G_l$ that start with edge $(u,v)$. Since the edge is present in all the components, it is never used in any of the Henneberg sequences. Hence, we can combine all the Henneberg sequences to a sequence for $G$. Hence, $G$ is Laman.

The second case is similar. Since $(u,v)$ is not present in $G_1$, the edge is used in the sequence for $G_1$, but not in any of the sequences for $G_2+(u,v),\mathrm{\dots },G_{\mathrm{\ell }}+(u,v)$. Hence, we can again combine all the Henneberg sequences to a sequence for $G$. Hence, $G$ is Laman. $◀$

The above lemma motivates us to define an operation on 2-connected graphs, which we call Laman-split.

For a Laman graph, all split graphs $G_i$ in Definition 21 have either $2n(G_i)-4$ or $2n(G_i)-3$ edges by Lemma 20. Note that we define the Laman-split also for graphs that are not Laman. In this case, the split graphs can also have other numbers of edges. In such a case, $G_i$, and hence $G$, are trivially detected as not being Laman.

Recall that by Lemma 7, the standard splitting of $2$-connected graphs in triconnected components is unique, i.e. independent of the order of the separating pairs we do the splitting. The following lemma shows when we apply Laman-splits to the components on the way, the resulting Laman components are unique as well.

Consider the standard recursive splitting procedure to compute the triconnected component tree of $G$. When we have split along a separating pair $\{u,v\}$, we can also compute the Laman-split that says in which split components edge $(u,v)$ should be put. Note that the recursive splitting is always done on the components computed by the standard splitting procedure. The Laman-split is a post-computation on these components that does not affect the recursive splitting. By the characterization given in Lemma 20, we conclude that $G$ is Laman iff all the components computed by Laman-splits are Laman.

It remains to argue about the uniqueness of the Laman decomposition. This property is crucial for our parallel algorithm to compute the decomposition. So assume that $G$ is a Laman graph. By Lemma 7, the triconnected components are unique. We argue that also the corresponding components we get from Laman-splits are uniquely determined. That is, whether a separating pair edge is present or not in a component is irrespective of the order of the decomposition.

This is trivial in case a separating pair $\{u,v\}$ is connected by an edge $(u,v)$ in $G$. Then all components will have the edge $(u,v)$ as well by Lemma 20. We only have to argue for the case that $\{u,v\}$ is not connected by an edge in $G$. In this case, the edge $(u,v)$ will be present in all but one of the components by Lemma 20. We argue that the component without edge $(u,v)$ is uniquely determined.

Consider the triconnected component tree $𝒯$. We argue via induction on the number of component nodes in $𝒯$. If $𝒯$ has just one component node, then there is no separating pair and the claim is trivial.

In the inductive step, let $𝒯$ have more than one component node. Let $C$ be a component node with a separating pair $\{u,v\}$ such that all other split components at $\{u,v\}$ are leafs in $𝒯$. In the leaf components $\{u,v\}$ is the only separating pair. Hence, it is uniquely defined whether the separating pair edge should be present in a leaf component or not, so that it has the right number of edges to be Laman. Therefore the same holds for the parent component $C$ by Lemma 20. Note also that the presence or absence of a separating pair edge $(u,v)$ in $C$ is not affected when $C$ is further split along a different separating pair.

Now we can prune the leaf components considered above from $𝒯$ and get a tree with a smaller number of component nodes where we can apply the induction hypothesis.

For the complexity bound, we describe a parallel procedure to obtain the Laman components. First we compute all triconnected components in ${\mathrm{𝖭𝖢}}^2$ (Lemma 8). To determine where to put the separating pair edges, we do a Laman-split of $G$, for every separating pair $\{u,v\}$ in parallel. That is, we treat each separating pair as the starting point of a Laman decomposition of $G$. Thereby we will put the edges correctly in the respective components by the uniqueness property: For any triconnected component $H$ that contains $\{u,v\}$, we add the separating pair edge $(u,v)$ to $H$, if after Laman-split in $G$ the component $H^{\prime }$ that contains $H$ has edge $(u,v)$. $◀$

Now we have all the tools to decide efficiently in parallel whether a given $K_{3,3}$-free graph is Laman.

Given a 2-connected $K_{3,3}$-free graph $G$, we apply the algorithm from Lemma 22 to compute its Laman components. Here we might already detect that $G$ is not Laman when the Laman-split yields some component where the number of edges does not match the number according to Lemma 20. Otherwise, we have that $G$ is Laman iff all the components are Laman. Note that the components are planar graphs or subgraphs of $K_5$ by Theorem 10, because separating pair edges only replace virtual edges, and hence do not affect planarity. Thus, we can apply Theorem 19 for all components in parallel to check if they are all Laman. All the subroutines used are in ${\mathrm{𝖭𝖢}}^2$. $◀$

The decision algorithm splits the graph $G$ along separating pairs until all components are planar and then checks that these components are Laman. We observed in Section 3 that we can also compute rigid embeddings for the planar components. To find a rigid embedding of $G$, we now want to reassemble the embeddings of the components appropriately.

In Lemma 24, we make the assumption that the two nodes of a separating pair are mapped to the same pair of points in all the components, respectively. We show that then we directly have a rigid embedding for the whole graph $G$.

We prove the claim for $\mathrm{\ell }=2$. For larger $\mathrm{\ell }$, we can iterate the argument, combining two graphs in every round. By Lemma 20, edge $(u,v)$ is not contained in at most one of the components. Hence, we may assume that $(u,v)$ is contained in $G_2$.

When we combine the rigidity matrices $R_1=R(G_1,p_1)$ and $R_2=R(G_2,p_2)$ as shown in Figure 2, we essentially get the rigidity matrix $R=R(G,p)$.

By our assumption, edge $(u,v)$ is in $G_2$ and hence, there is a row $(u,v)$ in $R_2$. Since $R_2$ has full rank, row $(u,v)$ is linearly independent from the other rows of $R_2$.

• $\mathrm{■}$

  If $(u,v)\in E$, then also $R_1$ and $R$ have a row $(u,v)$, and the row is linearly independent of the other rows of $R_1$ as well.

• $\mathrm{■}$

  If $(u,v)\notin E$, then row $(u,v)$ is present only in $R_2$, but not in $R_1$ and $R$. Now, row $(u,v)$ might be linearly dependent on the rows of $R_1$.

We have to show that the rows of matrix $R$ are linearly independent. Let $R_2^{\prime }$ denote the matrix consisting of all rows of $R_2$ except row $(u,v)$. Recall that if row $(u,v)$ belongs to $R$ then it also belongs to $R_1$. Hence, the rows of $R$ can be partitioned into $R_1$ and $R_2^{\prime }$. Since $R_1$ and $R_2^{\prime }$ have full rank, the only way we can have a dependency in $R$ is that there is a non-zero vector $a$ that is in the row-span of $R_1$ and of $R_2^{\prime }$ as illustrated in Figure 2. Then $a-a=0$ would give a non-trivial linear combination of the rows of $R$ that produces the zero vector.

By the structure of $R$ as shown in Figure 2, the only non-zero entries of $a$ can be at positions $u$ and $v$. We restrict our attention to these positions. Let $a_{u,v}$ and $b_{u,v}$ be the the part of $a$ and row $(u,v)$ at positions $u$ and $v$, respectively,

By assumption, we have $b_{u,v}\ne 0$. Let $M$ be the matrix consisting of the vectors for the three trivial motions, $M=(v_x,v_y,v_r)$, on these four positions. That is

Because $a$, and hence $a_{u,v}$ are a linear combination of the rows of the rigidity matrix, we have

Note that $M$ is $4\times 3$ matrix and $\mathrm{rank}(M)=3$ since we assume that $(x_u,y_u)\ne (x_v,y_v)$. Hence, the kernel of $M^T$ has dimension $1$. It follows that $a_{u,v}$ must be a multiple of $b_{u,v}$. Hence, vector $a$ is a multiple of the row-vector $(u,v)$ of $R$. But recall that $a$ is in the row-span of $R_2^{\prime }$ and row-vector $(u,v)$ is linearly independent of $R_2^{\prime }$. Hence, we must have $a=0$. Therefore, the rigidity matrix $R$ has full rank. $◀$

To get a rigid embedding of a $K_{3,3}$-free Laman graph, it now remains to show how to achieve the assumption of Lemma 24.

We follow the algorithm from Theorem 23 and apply Lemma 22 to decompose $G$ into planar Laman components $C_1,C_2,\mathrm{\dots },C_k$. Then we compute infinitesimally rigid embeddings $p_1,p_2,\mathrm{\dots },p_k$ for the components in parallel by Theorem 19.

The vertices that belong to some separating pair occur in several components. We will construct new rigid embeddings $q_1,q_2,\mathrm{\dots },q_k$ that will map different copies of any such vertex to the same point, and leave all other vertices unchanged. Then $q_1,q_2,\mathrm{\dots },q_k$ will fulfill the assumption of Lemma 24, and $q={\bigcup }_{i=1}^k{q}_i$ will be a rigid embedding for $G$.

For $v\in V$, let

For every $v\in V$ where $|S_v|>1$, we construct a pair of univariate polynomials $(a_v(t),b_v(t))$ that interpolates the points $\{p_i(v)\mid i\in S_v\}$. That is, we compute the interpolation polynomials such that $(a_v(i),b_v(i))=p_i(v)$, for every $i\in S_v$. Then we replace the coordinates of such a vertex $v$ by $(a_v(t),b_v(t))$ in each component. That is, we define embeddings $p_{i,t}(v)$, for $i\in [k]$ and $v\in V(C_i)$,

Note that a component $C_i$ can have several separating pair nodes and we replace their coordinates by different polynomials, respectively, but all in the same variable $t$. The interpolation guarantees that $p_{i,t}(v)$ agrees with $p_i(v)$ for $t=i$, for every $v\in V(C_i)$,

Consider the rigidity matrices $R(C_i,p_{i,t})$, where some of the entries are polynomials in $t$. Our goal is to find a value for $t$ such that all matrices $R(C_i,p_{i,t})$ have full rank. Let $R_i$ be a non-singular $(2n_i-3)$-square submatrix of $R(C_i,p_i)$ and define $R_{i,t}$ as the corresponding submatrix of $R(C_i,p_{i,t})$. Since $det(R_i)\ne 0$ and $R_i=R_{i,i}$ by (28), we have that $det(R_{i,t})$ is a non-zero polynomial. Hence, the product

is a non-zero polynomial too. For the degree of $A(t)$ note that $\mathrm{deg}(a_v),\mathrm{deg}(b_v)=|S_v|-1\le n.$ Therefore

Hence, for $A(t)$ we get

It follows that we can find a $t_0\in [2n^3+1]$ such that $A(t_0)\ne 0$. Now we define $q_i=p_{i,t_0}$, for all $i\in [k]$. By construction, $q_i$ is still a rigid embedding of $C_i$. Then $q={\bigcup }_{i=1}^k{q}_i$ is a rigid embedding for $G$ by Lemma 24.

For the complexity, note that polynomial interpolation and evaluation is in ${\mathrm{𝖭𝖢}}^2$ [13]. $◀$

The argument goes along the lines of the proof of Lemma 20, extended to triples.

Let $G$ be Laman. By Corollary 18, there is a Henneberg construction for $G$ that starts either with triangle $(u,v,w)$, or with one component, say $G_1=(V_1,E_1)$, where $|E_1(T)|=0$.

• $\mathrm{■}$

  If the sequence starts with triangle $(u,v,w)$, each triangle edge $e\in {\mathrm{\Delta }}_T-E(T)$ will be subdivided by a type $2$ step, adding a vertex in one split component, say $G_i$. Hence, to get a Henneberg sequence for all the components, we have to add $e$ to all of them except $G_i$.

• $\mathrm{■}$

  If the sequence starts by constructing $G_1$, the rest of the sequence constructs $G_2,\mathrm{\dots },G_{\mathrm{\ell }}$ by extending from $T$, but without using any triangle edges, because $|E_1(T)|=0$. Hence, we get Henneberg sequences for $G_2+{\mathrm{\Delta }}_T,\mathrm{\dots },G_{\mathrm{\ell }}+{\mathrm{\Delta }}_T$.

For the reverse direction, we have Henneberg sequences for all the components, where we have added the edges from ${\mathrm{\Delta }}_T-E(T)$ to $G_1,G_2,\mathrm{\dots },G_{\mathrm{\ell }}$, as described in the lemma. If all components have a Henneberg sequence that starts with triangle $(u,v,w)$, then we can combine them to one sequence for $G$. If there is component, say $G_1=(V_1,E_1)$ with $|E_1(T)|=0$, that cannot be constructed from triangle $(u,v,w)$, we start with the sequence for $G_1$. By definition, the other components are $G_2+{\mathrm{\Delta }}_T,\mathrm{\dots },G_{\mathrm{\ell }}+{\mathrm{\Delta }}_T$, that have Henneberg sequences starting with triangle $(u,v,w)$. These sequences will not use any triangle edge, and hence, we can attach them to the sequence for $G_1$. This yields a sequence for $G$. $◀$

When applying Lemma 26, we will consider different choices of triangle edges that can be added to make a component Laman. For three nodes in $G$ with no edge between them, there are three choices to add two edges between them. The following lemma states that when two of the choices make the graph Laman, then so does the third one.

Assume that $G+\{(u,w),(v,w)\}$ is not Laman. Then there must be a subset $S$ of vertices including at least two triple vertices such that

Then $S$ will also satisfy (32) in $G+\{(u,v),(u,w)\}$ or $G+\{(u,v),(v,w)\}$, a contradiction. $◀$

Consider the $4$-connected component tree of a $3$-connected graph. Let components $H_1,\mathrm{\dots },H_{\mathrm{\ell }}$ be leaf nodes in the tree that are attached via a common separating triple to parent component $H_0$. The following lemma shows how to prune the leafs in the tree and replace them by a constant size gadget in $H_0$ such that the Laman property is maintained.

Let ${\mathrm{\Delta }}_T=\{(u,v),(v,w),(u,w)\}$ be the triangle edges on $T$. Lemma 26 describes how to put the triangle edges of ${\mathrm{\Delta }}_T-E(T)$ in split components for graph $H$ to be Laman. However, this does not uniquely determine the placement of the edges. Therefore we consider all possibilities to put the edges that are consistent with Lemma 26.

Let ${ℱ}_0$ be the family of those sets $F_0\subseteq {\mathrm{\Delta }}_T-E(T)$ for which there exist sets $F_1,F_2,\mathrm{\dots },F_{\mathrm{\ell }}\subseteq {\mathrm{\Delta }}_T-E(T)$ such that

1. 1.

   each edge in ${\mathrm{\Delta }}_T-E(T)$ appears in all but one of $F_0,F_1,\mathrm{\dots },F_{\mathrm{\ell }}$ and

2. 2.

   $H_1+F_1,H_2+F_2,\mathrm{\dots },H_{\mathrm{\ell }}+F_{\mathrm{\ell }}$ are all Laman.

By Lemma 26, we have

We claim that the family ${ℱ}_0$ can be computed in ${\mathrm{𝖭𝖢}}^2$. To see this observe that the number of possible tuples $(F_0,F_1,\mathrm{\dots },F_{\mathrm{\ell }})$ which satisfy item 1 above is ${(\mathrm{\ell }+1)}^{|{\mathrm{\Delta }}_T-E(T)|}\le {(\mathrm{\ell }+1)}^3$. For all such tuples, we can check in parallel the Lamanness of $H_j+F_j$, for all $j\in [\mathrm{\ell }]$. Since $H_1,H_2,\mathrm{\dots },H_{\mathrm{\ell }}$ are planar or of bounded treewidth (with all virtual edges), we can invoke the ${\mathrm{𝖭𝖢}}^2$-algorithm from Theorem 19 or Theorem 5 to check whether $H_j+F_j$ is Laman.