Abstract A d -dimensional tensegrity framework ( T , p ) is an edge-labeled geometric graph in $$\mathbb {R}^d$$ R d , which consists of a graph $$T=(V,B\cup C\cup S)$$ T = ( V , B ∪ C ∪ S ) and a map $$p:V\rightarrow \mathbb {R}^d$$ p : V → R d . The labels determine whether an edge uv of T corresponds to a fixed length bar in ( T , p ), or a cable which cannot increase in length, or a strut which cannot decrease in length. We consider minimally infinitesimally rigid d -dimensional tensegrity frameworks and provide tight upper bounds on the number of its edges, in terms of the number of vertices and the dimension d . We obtain stronger upper bounds in the case when there are no bars and the framework is in generic position. The proofs use methods from convex geometry and matroid theory. A special case of our results confirms a conjecture of Whiteley from 1987. We also give an affirmative answer to a conjecture concerning the number of edges of a graph whose three-dimensional rigidity matroid is minimally connected.

Abstract. Given a graph [Formula: see text], a cost function on the non-edges of [Formula: see text], and an integer [Formula: see text], the problem of finding a cheapest globally rigid supergraph of [Formula: see text] in [Formula: see text] is NP-hard for [Formula: see text]. For this problem, which is a common generalization of several well-studied graph augmentation problems, no approximation algorithm has previously been known for [Formula: see text]. Our main algorithmic result is a 5-approximation algorithm in the [Formula: see text] case. We achieve this by proving numerous new structural results on rigid graphs and globally linked vertex pairs. In particular, we show that every rigid graph in [Formula: see text] has a tree-like structure, which conveys all the information regarding its globally rigid augmentations. Our results also yield a new, simple solution to the minimum cardinality version (where the cost function is uniform) for rigid input graphs, a problem which is known to be solvable in polynomial time.

Abstract. A [Formula: see text]-dimensional framework is a pair [Formula: see text], where [Formula: see text] is a graph and [Formula: see text] maps the vertices of [Formula: see text] to points in [Formula: see text]. The edges of [Formula: see text] are mapped to the corresponding line segments. A graph [Formula: see text] is said to be globally rigid in [Formula: see text] if every generic [Formula: see text]-dimensional framework [Formula: see text] is determined, up to congruence, by its edge lengths. A finer property is global linkedness: we say that a vertex pair [Formula: see text] of [Formula: see text] is globally linked in [Formula: see text] in [Formula: see text] if in every generic [Formula: see text]-dimensional framework [Formula: see text] the distance between [Formula: see text] and [Formula: see text] is uniquely determined by the edge lengths. In this paper we investigate globally linked pairs in graphs in [Formula: see text]. We give several characterizations of those rigid graphs [Formula: see text] in which a pair [Formula: see text] is globally linked if and only if there exist [Formula: see text] internally disjoint paths from [Formula: see text] to [Formula: see text] in [Formula: see text]. We call these graphs [Formula: see text]-joined. Among others, we show that [Formula: see text] is [Formula: see text]-joined if and only if for each pair of generic frameworks of [Formula: see text] with the same edge lengths, one can be obtained from the other by a sequence of partial reflections along hyperplanes determined by [Formula: see text]-separators of [Formula: see text]. We also show that the family of [Formula: see text]-joined graphs is closed under edge addition, as well as under gluing along [Formula: see text] or more vertices. As a key ingredient to our main results, we prove that rigid graphs in [Formula: see text] contain no crossing [Formula: see text]-separators. Our results give rise to new families of graphs for which global linkedness (and global rigidity) in [Formula: see text] can be tested in polynomial time.

A rigid graph G is said to be k-vertex (resp. k-edge) rigid in Rd if it remains rigid after the removal of less than k vertices (resp. edges). The definition of k-vertex (resp. k-edge) globally rigid graphs in Rd is similar. We study each of these four versions of redundant (global) rigidity and determine the smallest number of edges in a k-vertex (resp. k-edge) rigid (resp. globally rigid) graph on n vertices in R3 for all positive integers k, except for four special cases, where we provide a close-to-tight bound.

In the random subgraph model we consider random subgraphs $G(t)$ of a graph $G$ obtained as follows: for each edge in $G$ we independently decide to retain the edge with probability $t$ and discard the edge with probability $1-t$ for some $0\leq t\leq 1$. A special case of this model is the Erdös--Rényi random graph model, where the host graph is the complete graph $K_n$. In this paper we analyze the rigidity properties of random subgraphs and give new upper bounds on the threshold $t_0$ for which $G(t)$ is asymptotically almost surely (a.a.s.) rigid or globally rigid when $t\geq t_0$. By specializing our results to complete host graphs we obtain, among others, that an Erdös--Rényi random graph is a.a.s. globally rigid in $\mathbb{R}^d$ if $t\geq \frac{C_d\log n}{n}$ for some constant $C_d$. We also consider random subframeworks of (bar-and-joint) frameworks, which are geometric realizations of our graphs. Our bounds for the rigidity threshold of random subgraphs are in terms of the smallest nonzero eigenvalue of the stiffness matrix of the framework, which is the Gramian of its normalized rigidity matrix. Motivated by this connection, we introduce the concept of $d$-dimensional algebraic connectivity of graphs and provide upper and lower bounds for this value of several fundamental graph classes. The case $d=1$ corresponds to the well-known algebraic connectivity, that is, the second smallest Laplacian eigenvalue of the graph. We also consider the rigidity threshold in random molecular graphs, also called bond-bending networks, which are used in the study of rigidity properties of molecules. In this model we are concerned with the rigidity of the square graph of some graph $G$. We give an upper bound for the rigidity threshold of the square of random subgraphs in terms of the algebraic connectivity of the host graph. This enables us to derive an upper bound for the rigidity threshold for sparse host graphs.

The characterization of rigid graphs in Rd is known only in the low dimensional cases (d=1,2) and is a major open problem in higher dimensions. In this note we consider the other extreme case when d is close to n, the number of vertices of the graph. It turns out that there is a fairly simple characterization as long as n−d is at most four. We also characterize globally rigid graphs in this range.

Abstract A d-dimensional framework is a pair (G, p), where $$G=(V,E)$$ G = ( V , E ) is a graph and p is a map from V to $$\mathbb {R}^d$$ R d . The length of an edge $$uv\in E$$ u v ∈ E in (G, p) is the distance between p(u) and p(v). The framework is said to be globally rigid in $$\mathbb {R}^d$$ R d if every other d-dimensional framework (G, q), in which the corresponding edge lengths are the same, is congruent to (G, p). In a recent paper Gortler, Theran, and Thurston proved that if every generic framework (G, p) in $$\mathbb {R}^d$$ R d is globally rigid for some graph G on $$n\ge d+2$$ n ≥ d + 2 vertices (where $$d\ge 2$$ d ≥ 2 ), then already the set of (unlabeled) edge lengths of a generic framework (G, p), together with n, determine the framework up to congruence. In this paper we investigate the corresponding unlabeled reconstruction problem in the case when the above generic global rigidity property does not hold for the graph. We provide families of graphs G for which the set of (unlabeled) edge lengths of any generic framework (G, p) in d-space, along with the number of vertices, uniquely determine the graph, up to isomorphism. We call these graphs weakly reconstructible. We also introduce the concept of strong reconstructibility; in this case the labeling of the edges is also determined by the set of edge lengths of any generic framework. For $$d=1,2$$ d = 1 , 2 we give a partial characterization of weak reconstructibility as well as a complete characterization of strong reconstructibility of graphs. In particular, in the low-dimensional cases we describe the family of weakly reconstructible graphs that are rigid but not redundantly rigid.

A $d$-dimensional bar-and-joint framework $(G,p)$, where $G$ is a graph and $p$ maps the vertices of $G$ to points in $\mathbb{R}^d$, is said to be globally rigid if every $d$-dimensional framework $(G,q)$ with the same graph and same edge lengths is congruent to $(G,p)$. Global rigidity of frameworks and graphs is a well-studied area of rigidity theory with a number of applications, including the localization problem of sensor networks. Motivated by this application we consider the new notion of unit ball global rigidity, which can be defined similarly, except that $(G,p)$ as well as $(G,q)$ are required to be unit ball frameworks in the above definition. In a unit ball framework two vertices are adjacent if and only if their distance is less than a fixed constant (which corresponds to the sensing radius in a sensor network). In this paper we initiate a theoretical analysis of this version of global rigidity and prove several structural results. Among others we identify families of frameworks (and corresponding graphs $G$) in $\mathbb{R}^d$ for all $d\geq 1$ which are unit ball globally rigid without being globally rigid in the usual sense. These families contain minimally rigid graphs, too, which have fewer edges than any of the globally rigid graphs on the same number of vertices.

We consider planar bar-and-joint frameworks with discrete point group symmetry in which the joint positions are as generic as possible subject to the symmetry constraint. We provide combinatorial characterizations for symmetry-forced rigidity of such structures with rotation symmetry or dihedral symmetry of order 2 k with odd k , unifying and extending previous work on this subject. We also explore the matroidal background of our results and show that the matroids induced by the row independence of the orbit matrices of the symmetric frameworks are isomorphic to gain sparsity matroids defined on the quotient graph of the framework, whose edges are labeled by elements of the corresponding symmetry group. The proofs are based on new Henneberg type inductive constructions of the gain graphs that correspond to the bases of the matroids in question, which can also be seen as symmetry preserving graph operations in the original graph.

We consider the problems of completing a low-rank positive semidefinite square matrix $M$ or a low-rank rectangular matrix $N$ from a given subset of their entries. Following the approach initiated by Singer and Cucuringu [SIAM J. Matrix Anal. Appl., 31 (2010), pp. 1621--1641] we study the local and global uniqueness of such completions by analyzing the structure of the graphs determined by the positions of the known entries of $M$ or $N$. We present combinatorial characterizations of local and global (unique) completability for special families of graphs. We characterize local and global completability in all dimensions for cluster graphs, i.e. graphs which can be obtained from disjoint complete graphs by adding a set of independent edges. These results correspond to theorems for body-bar frameworks in rigidity theory. We also provide a characterization of two-dimensional local completability of planar bipartite graphs, which leads to a characterization of two-dimensional local completability in the rectangular matrix model when the underlying bipartite graph is planar. These results are based on new observations that certain graph operations preserve local or global completability, as well as on a further connection between rigidity and completability. We also prove that a rank condition on the completability stress matrix of a graph is a sufficient condition for global completability. This verifies a conjecture of Singer and Cucuringu given in the paper cited above.

Let $(G,p)$ be a minimally infinitesimally rigid $d$-dimensional bar-and-joint framework and let $L$ be an equilibrium load on $p$. The load can be resolved by appropriate stresses in the bars of the framework. Our goal is to identify the following parts (zones) of the framework: (i) When the location of an unloaded joint $v$ is perturbed, and the same load is applied, the stress will change in some of the bars. We call the set of these bars the influenced zone of $v$. (ii) Let $S$ be a designated set of joints and suppose that each joint with a nonzero load belongs to $S$. The active zone of $S$ is the set of those bars in which the stress, which resolves $L$, is nonzero. We prove that if $(G,p)$ is generic, then for almost all loads these zones depend only on the graph $G$ of the framework. These results are extended to arbitrary infinitesimally rigid generic frameworks. We also show that for $d=2$ these zones can be computed by efficient combinatorial methods.

Abstract The concept of persistent directed graphs was introduced by Hendrickx et al. to help analyze the stability of autonomous agent systems. They provided a combinatorial characterization for persistence but the complexity of testing persistence remained open. In this note we show that for directed graphs D with ∑vεV(D) min{δD(v), 2} ≤ 2∣V(D)∣ − 3 persistence can be tested in polynomial time, where δD(v) denotes the out‐degree of vertex v in D. This family of directed graphs includes acyclic digraphs (for which an efficient algorithm was known) as well as all digraphs with a leader‐follower structure. We also discuss some related orientation problems. Among others we point out that the existence of an acyclic persistent orientation can be tested in polynomial time for all graphs. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Splitting off two edges su,sv in a graph G means deleting su,sv and adding a new edge uv. Let G=(V+s,E) be k-edge-connected in V ($k\geq 2$) and let d(s) be even. Lovász proved that the edges incident to s can be split off in pairs in a such a way that the resulting graph on vertex set V is k-edge-connected. In this paper we investigate the existence of such complete splitting sequences when the set of split edges has to meet additional requirements. We prove structural properties of the set of those pairs u,v of neighbors of s for which splitting off su,sv destroys k-edge-connectivity. This leads to a new method for solving problems of this type. By applying this method we obtain a short proof for a recent result of Nagamochi and Eades on planarity-preserving complete splitting sequences and prove the following new results: let G and H be two graphs on the same set V+s of vertices and suppose that their sets of edges incident to s coincide. Let G (H) be k-edge-connected (l-edge-connected, respectively) in V ($k,l\geq 2$) and let d(s) be even. Then there exists a pair su,sv which can be split off in both graphs preserving k-edge-connectivity in G (l-edge-connectivity in H, respectively), provided $d(s)\geq 6$. If k and l are both even, then such a pair always exists. By using these edge-splitting results and the polymatroid intersection theorem we give a polynomial algorithm for the problem of simultaneously augmenting the edge-connectivity of two graphs by adding a (common) set of new edges of (almost) minimum size.

Let G=(V+s,E) be a graph with a designated vertex s of degree d(s), and let f(s)=(d 1 ,d 2 ,. . .,d p ) be a partition of d(s) into p positive integers. An f(s)-detachment of G is a graph G' obtained by "splitting" s into p vertices, called the pieces of s, such that the degrees of the pieces of s in G' are given by f(s). Thus every edge $sw\in E$ corresponds to an edge of G' connecting some piece of s to w. We give necessary and sufficient conditions for the existence of an f(s)-detachment of G in which the local edge-connectivities between pairs of vertices in V satisfy prespecified lower bounds. Our result is a common generalization of a theorem of Mader on edge splittings preserving local edge-connectivities and a result of Fleiner on f(s)-detachments satisfying uniform lower bounds. It implies a conjecture of Fleiner on f(s)-detachments preserving local edge-connectivities. By using our characterization we extend a theorem of Frank on local edge-connectivity augmentation of graphs to the case when stars of given degrees are added, and we also solve the local edge-connectivity augmentation problem for 3-uniform hypergraphs.

This paper solves the problem of making a bipartite digraph strongly connected by adding the smallest number of new edges that preserve bipartiteness. A result of Baglivo and Graver shows that this corresponds to making a two-dimensional square grid framework with cables rigid by adding the smallest number of new cables. We prove a min-max formula for the smallest number of new edges in the digraph problem and give a corresponding linear-time algorithm. We generalize these results to the problem of making an arbitrary digraph strongly connected by adding the smallest number of new edges, each of which joins vertices in distinct blocks of a given partition of the vertex set.

In the well-solved edge-connectivity augmentation problem we must find a minimum cardinality set F of edges to add to a given undirected graph to make it k-edge-connected. This paper solves the generalization where every edge of F must go between two different sets of a given partition of the vertex set. A special case of this partition-constrained problem, previously unsolved, is increasing the edge-connectivity of a bipartite graph to k while preserving bipartiteness. Based on this special case we present an application of our results in statics. Our solution to the general partition-constrained problem gives a min-max formula for |F| which includes as a special case the original min-max formula of Cai and Sun [Networks, 19 (1989), pp. 151--172] for the problem without partition constraints. When k is even the min-max formula for the partition-constrained problem is a natural generalization of the unconstrained version. However, this generalization fails when k is odd. We show that at most one more edge is needed when k is odd and we characterize the graphs that require such an extra edge. We give a strongly polynomial algorithm that solves our problem in time O(n(m + nlog n)log n). Here n and m denote the number of vertices and distinct edges of the given graph, respectively. This bound is identical to the best-known time bound for the problem without partition constraints. Our algorithm is based on the splitting off technique of Lovász, like several known efficient algorithms for the unconstrained problem. However, unlike previous splitting algorithms, when k is odd our algorithm must handle obstacles that prevent all edges from being split off. Our algorithm is of interest even when specialized to the unconstrained problem, because it produces an asymptotically optimum number of distinct splits.

Given a simple graph G=(V,E), our goal is to find a smallest set F of new edges such that G=(V,E\cup F) is k-edge-connected and simple. Recently this problem was shown to be NP-complete. In this paper we prove that if OPT_P^k$ is high enough---depending on k only---then OPT _S^k= OPT_P^k$ holds, where OPT_S^k$ (OPT_P^k$) is the size of an optimal solution of the augmentation problem with (without) the simplicity-preserving requirement, respectively. Furthermore, OPT_S^k- OPT _P^k\leq g(k) holds for a certain (quadratic) function of k. Based on these facts an algorithm is given which computes an optimal solution in time O(n4) for any fixed k. Some of these results are extended to the case of nonuniform demands as well.

Given a simple graph G=(V, E), the goal is to find a smallest set F of new edges such that G=(V, E/spl cup/F) is /spl kappa/ edge connected and simple. Very recently this problem was shown to be NP hard by T. Jordan (1997). We prove that if OPT/sub P//sup /spl kappa// is high enough-depending on /spl kappa/ only-then OPT/sub S//sup /spl kappa//=OPT/sub P//sup /spl kappa// holds, where OPT/sub S//sup /spl kappa// (OPT/sub P//sup /spl kappa//) is the size of an optimal solution of the augmentation problem with (without) the simplicity preserving requirement, respectively. Furthermore, OPT/sub S//sup /spl kappa//-OPT/sub P//sup /spl kappa///spl les/g(/spl kappa/) holds for a certain (quadratic) function of /spl kappa/. Based on these results an algorithm is given which computes an optimal solution in time O(n/sup 4/) for any fixed /spl kappa/. Most of these results are extended to the case of non-uniform demands, as well.