ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P1.03
https://doi.org/10.26493/1855-3974.2800.d12
(Also available at http://amc-journal.eu)
Redundantly globally rigid braced
triangulations*
Qianfan Chen
Brown University, Providence, RI, USA
Siddhant Jajodia
University of California, Irvine, CA, USA
Tibor Jordán †
Department of Operations Research, ELTE Eötvös Loránd University, and
ELKH-ELTE Egerváry Research Group on Combinatorial Optimization, Eötvös Loránd
Research Network (ELKH), Pázmány Péter sétány 1/C, 1117 Budapest, Hungary
Kate Perkins
Harvey Mudd College, Claremont, CA, USA
Received 8 January 2022, accepted 23 January 2023, published online 9 August 2023
Abstract
By mapping the vertices of a graph G to points in R3, and its edges to the corresponding
line segments, we obtain a three-dimensional realization of G. A realization of G is said to
be globally rigid if its edge lengths uniquely determine the realization, up to congruence.
The graph G is called globally rigid if every generic three-dimensional realization of G is
globally rigid.
We consider global rigidity properties of braced triangulations, which are graphs ob-
tained from maximal planar graphs by adding extra edges, called bracing edges. We show
that for every even integer n ≥ 8 there exist braced triangulations with 3n− 4 edges which
remain globally rigid if an arbitrary edge is deleted from the graph. The bound is best pos-
sible. This result gives an affirmative answer to a recent conjecture. We also discuss the
connections between our results and a related more general conjecture, due to S. Tanigawa
and the third author.
*This paper is based on the results of a research opportunities project of the Budapest Semesters in Mathemat-
ics (BSM) programme.
†Corresponding author. The third author was supported by the Hungarian Scientific Research Fund grant no.
K135421 and the project Application Domain Specific Highly Reliable IT Solutions which has been implemented
with the support provided from the National Research, Development and Innovation Fund of Hungary, financed
under the Thematic Excellence Programme TKP2020-NKA-06 (National Challenges Subprogramme) funding
scheme.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P1.03
Keywords: Triangulation, globally rigid graph, braced triangulation, rigidity.
Math. Subj. Class. (2020): 52C25, 05C10
1 Introduction
A d-dimensional framework (or geometric graph) is a pair (G, p), where G is a simple
graph and p : V (G) → Rd is a map. We also call (G, p) a realization of G in Rd. The
length of an edge uv in the framework is defined to be the distance between the points p(u)
and p(v). The framework is said to be rigid in Rd if every continuous motion of its vertices
in Rd that preserves all edge lengths preserves all pairwise distances. It is globally rigid
in Rd if the edge lengths uniquely determine all pairwise distances. A realization (G, p)
is generic if the set of the d|V (G)| coordinates of the vertices is algebraically independent
over the rationals. It is known that for generic frameworks rigidity and global rigidity in
Rd depend only on the graph of the framework, for every d ≥ 1. So we may call a graph G
rigid (resp. globally rigid) in Rd if every (or equivalently, if some) generic d-dimensional
realization of G is rigid (resp. globally rigid). The characterization of rigid and globally
rigid graphs is known for d = 1, 2. For d ≥ 3 these are major open problems. We refer the
reader to [8, 10] for more details on the theory of rigid and globally rigid frameworks and
graphs.
Rigid and globally rigid graphs occur in several applications, including sensor network
localization [4], molecular conformation [3], formation control [13], and statics [9]. In
some applications it is desirable to have a graph which remains rigid or globally rigid even
if some vertices or edges are removed. In this paper we study graphs G for which G − e
is globally rigid in Rd for each edge e of G. They are called redundantly globally rigid in
Rd. In the rest of the paper we focus on the three-dimensional case, i.e. d = 3, and the
following two conjectures concerning redundant global rigidity.
A triangulation T = (V,E) is a maximal planar graph on at least three vertices. A
braced triangulation G = (V,E ∪B) is a graph obtained from a triangulation T = (V,E)
by adding a set B of new edges, called the bracing edges. If |B| = 1 (resp. |B| = 2) then
we say that G is a uni-braced (resp. doubly braced) triangulation. The characterization of
globally rigid braced triangulations in R3 is known, see Theorem 2.6 below. A conjectured
sufficient condition for redundant global rigidity is as follows.
Conjecture 1.1 ([7]). Every 5-connected braced triangulation G = (V,E∪B) with |B| ≥
2 is redundantly globally rigid in R3.
A related extremal problem is to determine the smallest number of edges in a redun-
dantly globally rigid graph in R3 on n vertices, as a function of n, for all (sufficiently large)
n. By a theorem of B. Hendrickson [3] every globally rigid graph G in Rd on n ≥ d + 2
vertices remains rigid in Rd after removing any edge of G. It is well-known that a rigid
graph in R3 on n ≥ 3 vertices has at least 3n − 6 edges. These facts imply that 3n − 4 is
a lower bound for the extremal value, and n ≥ 6 must hold. It was conjectured in [6] that
this lower bound is tight.
E-mail addresses: qianfan chen@alumni.brown.edu (Qianfan Chen), jajodias@uci.edu (Siddhant Jajodia),
tibor.jordan@ttk.elte.hu (Tibor Jordán), kperkins@hmc.edu (Kate Perkins)
Q. Chen et al.: Redundantly globally rigid braced triangulations 3
Conjecture 1.2 ([6]). For every integer k there exists a redundantly globally rigid graph
G in R3 on n ≥ k vertices with 3n− 4 edges.
The truth of Conjecture 1.1, combined with the fact that there exist arbitrarily large
5-connected triangulations, would imply Conjecture 1.2. We remark that W. Whiteley [12]
conjectured that every 5-connected doubly braced triangulation G remains rigid in R3 after
removing any pair of its edges. The truth of Conjecture 1.1, together with Hendrickson’s
theorem, would imply an affirmative answer to his conjecture.
In the rest of the paper – after introducing the results from rigidity theory that we shall
use – we consider doubly braced triangulations in which both bracing edges are dihedral
(i.e. they connect non-adjacent vertices that belong to edge sharing faces). We shall prove
sufficient conditions that guarantee that a specific edge can be removed from such a trian-
gulation while preserving global rigidity.
Based on these results we can analyse special families of such triangulations which will
lead to the proof of (a stronger form of) Conjecture 1.2. We shall prove that for every even
integer n ≥ 8 there exist redundantly globally rigid graphs in R3 on n vertices with 3n− 4
edges1. In the last section we prove necessary conditions for the redundant global rigidity
of braced triangulations and formulate a couple of conjectures.
2 Rigid and globally rigid graphs
We shall use the following results in order to verify the rigidity or global rigidity of a graph.
Let G = (V,E) be a graph. For a vertex v ∈ V let NG(v) (resp. dG(v)) denote the set
(resp. the number) of neighbours of v in G. For a set X ⊆ V the graph obtained from G
by adding a complete graph on vertex set X (that is, by adding new edges connecting the
vertex pairs x, y ∈ X which are not adjacent in G) is denoted by G+K(X).
Theorem 2.1 ([11]). Let G = (V,E) be a graph and v ∈ V with dG(v) ≥ d+1, for some
d ≥ 1. If G− v is rigid and G− v +K(NG(v)) is globally rigid in Rd then G is globally
rigid in Rd.
A bracing edge uv in a braced triangulation G is called dihedral if it connects two non-
adjacent vertices u, v of two edge sharing triangles on vertices uab and vab, respectively,
of the triangulation.
A block and hole graph is obtained from the graph of an (embedded) plane triangula-
tion by removing the interiors of some discs, defined by their boundary cycles, and then
rigidifying the vertex sets of some of these cycles by adding new edges. This operation
creates some holes and blocks. We shall only consider special block and hole graphs. By
removing a single edge or a vertex of degree five from an (embedded) triangulation, we
may create a face whose boundary is a 4-cycle or a 5-cycle, respectively. We shall say that
such a cycle is a 4-hole or 5-hole in (some planar embedding of) the graph. The addition
of a dihedral bracing edge creates a K4 subgraph, which can be viewed as a 4-block that
rigidifies the cycle aubv, provided the two edge sharing triangles uab, vab are both faces
in the embedding. Since we shall only consider 5-connected triangulations, these triangles
will always be faces (in any embedding) and the resulting 4-block will be uniquely defined.
For simplicity we shall call a braced triangulation with dihedral bracing edges and a re-
moved edge or degree-five vertex a block and hole graph. See [2, 12] for a more general
1We can extend our result to odd values of n by using different techniques. We do not discuss this extension
in this paper.
4 Ars Math. Contemp. 24 (2024) #P1.03
definition and results on rigid block and hole graphs in three-space. We need the following
corollaries of their results.
Theorem 2.2 ([12]). Let G be a 4-connected block and hole graph which has a single
4-hole and a single 4-block. Then G is rigid in R3.
Theorem 2.3 ([2]). Let G′ be a 5-connected block and hole graph with two 4-blocks and
let G = G′ − v, where v is a vertex of degree five in G′ which is disjoint from the blocks.
Then G is rigid in R3.
Let G be a graph and let uv, vw be a pair of incident edges in G. Let Evuw be the set of
the remaining edges incident with v and let Evuw = F ∪ F ′ be a bipartition of Evuw. The
(3-dimensional) vertex splitting operation (at v, on edges uv, vw) adds a new vertex v′ to
the graph, adds the new edges uv′, v′w, vv′, and then replaces every edge xv in F ′ by an
edge xv′. The edges in F stay incident to v. See Figure 1. The vertex splitting is said to be
non-trivial if F and F ′ are both non-empty.
u
w
v
u
w
v
v′
Figure 1: A non-trivial vertex splitting operation on edges uv, vw.
An important conjecture in rigidity theory is that non-trivial vertex splitting preserves
global rigidity in Rd, for all d ≥ 1, see [1]. The next result verifies a special case.
Theorem 2.4 ([7]). A graph is globally rigid in R3 if it can be obtained from K5 by a
sequence of non-trivial vertex splitting operations.
This theorem can be used in the analysis of globally rigid braced triangulations, due to
the following combinatorial result.
Theorem 2.5 ([7]). Every 4-connected uni-braced triangulation can be obtained from K5
by a sequence of non-trivial vertex splitting operations.
Thus 4-connected uni-braced triangulations are globally rigid. A complete characteri-
zation, with no bounds on the number of bracing edges, is the following.
Theorem 2.6 ([7]). A braced triangulation G = (V,E ∪B) with |V | ≥ 5 is globally rigid
in R3 if and only if G is 4-connected and |B| ≥ 1.
The inverse operation of vertex splitting is the contraction of an edge uv for which
u and v have exactly two common neighbours. This operation takes a triangulation to a
smaller triangulation. We shall also use the fact that an edge contraction decreases the
vertex connectivity of a graph by at most one.
Q. Chen et al.: Redundantly globally rigid braced triangulations 5
3 Redundant edges in braced triangulations
In this section we fix the dimension d = 3. Every 5-connected braced triangulation with at
least one bracing edge is globally rigid by Theorem 2.6. We shall describe several situations
in which the removal of an edge from a 5-connected braced triangulation preserves global
rigidity. The first lemma is an immediate corollary of Theorem 2.6.
Lemma 3.1. Let G = (V,E ∪ B) be a 5-connected braced triangulation with |B| ≥ 2.
Then G− e is globally rigid for every e ∈ B.
In the rest of this section we shall assume that G is a 5-connected graph obtained from
an (embedded) triangulation by adding exactly two dihedral bracing edges that create two
4-blocks, with at most two vertices in common.
Lemma 3.2. Let G = (V,E ∪ B) be a 5-connected doubly braced triangulation with two
4-blocks. Suppose that e = uv ∈ E is an edge with dG(v) = 5 and v is disjoint from the
4-blocks. Then G− e is globally rigid.
Proof. We shall prove that v satisfies the conditions of Theorem 2.1 in graph G − e. The
inequality dG−e(v) ≥ 4 is clearly satisfied. Since v is disjoint from the 4-blocks of G, the
graph (G− e)− v (= G− v) is a block and hole graph with one 5-hole and two 4-blocks.
The 5-connectivity of G and Theorem 2.3 imply that (G − e) − v is rigid. Next consider
the graph H = (G − e) − v +K(NG−e(v)). By 5-connectivity the four neighbours of v
in G− e induce three edges in G− e. Thus three new edges are added to G− e to obtain
H . Notice that H is a braced triangulation: two new edges can be used to triangulate the
graph obtained from T = (V,E) by removing v, while the third one becomes a bracing
edge. See Figure 2.
v
G - e G - e - v + K(N(G - e)(v))
K4
K4
K4
K4
Figure 2: The neighbourhood of v in G − e and the edges they induce in H . The dashed
edge is a bracing edge.
Since G is 5-connected, (G − e) − v = G − v is 4-connected. This implies that H
is 4-connected. Hence H is globally rigid by Theorem 2.6. The lemma now follows from
Theorem 2.1, applied to G− e and v.
6 Ars Math. Contemp. 24 (2024) #P1.03
Lemma 3.3. Let G = (V,E ∪ B) be a 5-connected doubly braced triangulation with two
4-blocks. Suppose that e = uv ∈ E is an edge with dG(v) = 5 and v belongs to exactly
one of the 4-blocks. Then G− e is globally rigid.
Proof. Suppose that the 4-blocks are C1 and C2, and v is part of C1, say. Then the deletion
of v from G − e creates a block and hole graph with a 4-block (namely, C2) and a 4-hole.
Note that if v is not incident with the bracing edge f of C1 then f becomes an edge of the
underlying (almost) triangulation of (G−e)−v. Since G is 5-connected, (G−e)−v = G−v
is 4-connected. Thus (G − e) − v is rigid by Theorem 2.2. Furthermore, it follows that
G−v+K(NG−e(v)) is a 4-connected braced triangulation with two bracing edges. Hence
it is globally rigid by Theorem 2.6.
The Lemma now follows from Theorem 2.1, applied to G− e and v.
Lemma 3.4. Let G = (V,E ∪ B) be a 5-connected doubly braced triangulation with two
4-blocks C1, C2 and let v ∈ V (C1) − V (C2). Suppose that vw ∈ E ∩ E(C1) for which
there is a triangular face uvw of T = (V,E) with u /∈ V (C1). Let e = uv. Then G− e is
globally rigid.
Proof. We show that G − e can be obtained from K5 by a sequence of non-trivial vertex
splitting operations. Observe that G − e has a 4-hole and two 4-blocks in which v and w
have exactly two common neighbours (the two other vertices of C1) by 5-connectivity. Let
H be the graph obtained from G−e by contracting the edge vw. It is easy to see that H is a
4-connected uni-braced triangulation. Thus H (and hence also G−e) can be obtained from
K5 by a sequence of non-trivial vertex splitting operations by Theorem 2.5. The Lemma
now follows from Theorem 2.4.
The last lemma of this section is concerned with the case when the two 4-blocks share
two vertices.
Lemma 3.5. Let G = (V,E∪B) be a 5-connected doubly braced triangulation with two 4-
blocks C1, C2 with V (C1)∩V (C2) = {a, b}, where V (C1) = {a, b, c, d}, and the dihedral
bracing edge in C1 is ad. Then G− ab and G− ac are globally rigid. Furthermore, if v is
a vertex which is disjoint from the blocks and cv, av ∈ E then G− av is globally rigid.
Proof. We have V (C1) − V (C2) = {c, d}. Let us consider the removal of edge e = ab.
Observe that in G−e the vertices c and a have exactly two common neighbours. Moreover,
the graph H obtained from G − e by contracting the edge ca is a 4-connected uni-braced
triangulation. Thus H (and hence also G − e) can be obtained from K5 by a sequence of
non-trivial vertex splitting operations by Theorem 2.5. Thus G − ab is globally rigid by
Theorem 2.4.
The proof for edge ac is similar. In this case we delete the edge ac, contract the edge
cd, and apply the same argument. Finally, to show that G − av is globally rigid, we use a
similar proof again in which we delete av and then contract ac.
4 Two families of graphs
In this section, we define two infinite families of redundantly globally rigid doubly braced
triangulations in R3.
Q. Chen et al.: Redundantly globally rigid braced triangulations 7
Definition 4.1 (Belted bipyramid). For every n ≥ 3, an n-gonal belted bipyramid, denoted
by G(n), is a graph on 2n+2 vertices that is constructed as follows. Take two n-gonal pyra-
mids with poles N and S, respectively, and label the vertices on the base of one pyramid 1
to n and on that of the other 1’ to n’ consecutively. Insert edges between the corresponding
pairs of vertices (i.e. between 1 and 1’, 2 and 2’, and so on) and insert an edge between k
and (k + 1)’ for every 1 ≤ k ≤ (n − 1). Finally, insert an edge between n and 1’. See
Figure 3.
It is easy to see that G(n) is a triangulation. Let G(n, k) denote the graph obtained by
inserting the edges 1n′ and k(k−1)′ to G(n). Then G(n, k) is a doubly braced triangulation
with two dihedral bracing edges. See Figure 3.
N
S
3
21
5
4
5’
1’ 2’
3’
4’
N
S
3
21
5
4
5’
1’ 2’
3’
4’
Figure 3: The graphs G(5) and G(5, 4).
Lemma 4.2. For every n ≥ 5, G(n) (and hence, G(n, k) for every 2 ≤ k ≤ n) is 5-
connected.
Proof. By using the structure and the symmetry of G(n) it is not hard to check that it is
5-connected. A simple argument is as follows: consider the base cycle C of one of the
8 Ars Math. Contemp. 24 (2024) #P1.03
pyramids on vertex set (1, 2, ..., n). It is easy to verify that for every v ∈ V − V (C)
there exist 5 paths from v to V (C) that are vertex-disjoint, apart from v. Furthermore, for
every u, v ∈ V (C) there exist 5 u-v-paths that are vertex-disjoint apart from u, v. Since
|V (C)| ≥ 5, this implies that G(n) cannot have a vertex separator of size less than 5.
Theorem 4.3. For every n ≥ 5 and 2 ≤ k ≤ n the graph G(n, k) is redundantly globally
rigid in R3.
Proof. Theorem 2.6 implies that G(n, k) is globally rigid in R3. It remains to show that
the removal of any edge preserves global rigidity. First suppose that 3 ≤ k ≤ n − 1, in
which case the two 4-blocks are disjoint.
Each bracing edge is redundant by Lemma 3.1. Note that each vertex has degree five in
G(n, k), except for the two poles (when n ≥ 6) and the end-vertices of the bracing edges.
Thus we can use Lemmas 3.2 and 3.3 to show that most of the edges are redundant. The
edges that do not satisfy the conditions of at least one of these two lemmas are the edges
from the poles to the end-vertices of the bracing edges and, possibly, an edge that connects
the end-vertices of different bracing edges. These edges are redundant by Lemma 3.4. So
every edge is redundant and the graph is redundantly globally rigid, as required.
We can also show that G(n, 2) and G(n, n) are redundantly globally rigid by a similar
argument. In these two special cases the two 4-blocks share two vertices, so we also need
Lemma 3.5 in order to handle some of the edges incident with the intersection of the blocks.
A slightly different construction is the following.
Definition 4.4 (Flat belted bipyramid). For every n ≥ 4, an n-gonal flat belted bipyramid,
denoted by F (n), is a graph on 2n vertices that is constructed as follows. Take G(n)
and delete its two poles. Retaining the vertex labels described in Definition 1, for every
1 ≤ k ≤ n, insert an edge between vertex 3 and vertex k (unless 3 is already adjacent to
k). Then, for every 1 ≤ k ≤ n, insert an edge between vertex 2′ and vertex k′ (unless 2’ is
already adjacent to k′). See Figure 4.
It is easy to see that F (n) is a triangulation. Let H(n) be the graph obtained from F (n)
by inserting edges 1′2 and 3′4. See Figure 4. Thus H(n) is a doubly braced triangulation
with two dihedral bracing edges that create two disjoint 4-blocks. Although F (n) is not
5-connected, a proof strategy similar to that of Lemma 4.2 can be used to show that H(n)
is 5-connected.
Lemma 4.5. For every n ≥ 4 the graph H(n) is 5-connected.
In fact we can show that H(4) is the smallest 5-connected doubly braced triangulation2.
Theorem 4.6. H(n) is redundantly globally rigid in R3 for n ≥ 4.
2The minimum degree condition implies that the number of vertices is at least eight, and equality holds only
if the graph is 5-regular. Thus the complement of the graph is isomorphic to one of the following: (i) the disjoint
union of a three-cycle and a five-cycle, (ii) the disjoint union of two four-cycles, (iii) a cycle on eight vertices. In
the first two cases a simple analysis shows that the graph cannot be made planar by removing at most two edges.
In the third case the graph is H(4).
Q. Chen et al.: Redundantly globally rigid braced triangulations 9
H5
3
21
5
4
5’
1’ 2’
3’
4’
H(5)
3
21
5
4
5’
1’ 2’
3’
4’
Figure 4: The graphs F (5) and H(5).
Proof. Theorem 2.6 implies that H(n) is globally rigid in R3. It remains to show that the
removal of any edge preserves global rigidity. The rest of the proof is similar to that of
Theorem 4.3, using the lemmas of the previous section. Note that in the case of H(n) the
two 4-blocks are disjoint.
The results of this section provide an affirmative answer to Conjecture 1.2.
Theorem 4.7. For every even integer n ≥ 8 there exist redundantly globally rigid graphs
in R3 on n vertices with 3n− 4 edges.
A simple degree count shows that there are no such graphs for n ≤ 7.
As we noted earlier, redundantly globally rigid graphs are “doubly redundantly rigid”,
that is, they remain rigid after the removal of any pair of edges. Thus the graphs defined in
this section are also examples of doubly redundantly rigid graphs with the smallest number
of edges for every even n ≥ 8. They are different from the ones constructed in [6], and
easier to analyse.
10 Ars Math. Contemp. 24 (2024) #P1.03
5 Concluding remarks and conjectures
A natural question is whether the 5-connectivity condition in Conjecture 1.1 can be weak-
ened. The next example shows that 5-connectivity is not necessary.
Example 5.1. Consider the graph G in Figure 5. It is a 4-connected (but not 5-connected)
doubly braced triangulation, and hence it is globally rigid by Theorem 2.6. We sketch a
proof which shows that G− e is globally rigid for every edge e. By the symmetry of G we
have four cases to consider: the deleted edge e is
(i) a cross edge in the top K4,
(ii) a side in the top K4,
(iii) an edge from the K4 to the 4-cycle of the 4-separator,
(iv) an edge of the 4-cycle of the separator.
In case (i) G− e is a 4-connected braced triangulation. In cases (ii) and (iii) we can apply
(the proof of) Lemma 3.3 by noting that its proof works here by using the specific structure
of G (rather than 5-connectivity). In case (iv) we perform two contractions and obtain a
4-connected uni-braced triangulation as follows. Suppose, by symmetry, that e = cd. Then
first contract an edge between c and the top K4. Next contract one of the edges from c to
the remainder of the top K4. By contracting the appropriate edge we obtain a 4-connected
uni-braced triangulation. Then global rigidity follows by Theorem 2.4.
This leads us to the next question: is it possible to obtain a complete characterization
of redundantly globally rigid braced triangulations, at least in some special cases (say, for
doubly braced triangulations with two dihedral bracing edges)?
a b c d
G
C2
C1
Figure 5: A redundantly globally rigid doubly braced triangulation G with a 4-separator
S = {a, b, c, d}.
In this section we prove some necessary conditions and then formulate a conjecture.
A k-separator S in a connected graph G = (V,E) is a set of vertices with |S| = k for
which G − S is disconnected. For some X ⊆ V we use G[X] to denote the subgraph of
Q. Chen et al.: Redundantly globally rigid braced triangulations 11
G induced by vertex set X . It is known that for a minimal separator S in a triangulation G
we have |S| ≥ 3, the graph G − S has exactly two connected components, and G[S] is a
cycle (see e.g. [7, Section 5]). For a separator S and connected component C of G− S we
say that G[C ∪ S] is an extended component of S in G.
Lemma 5.2. Let G = (V,E ∪ B) be a redundantly globally rigid braced triangulation
and let S be a 4-separator in G. Suppose that S is a minimal separator in the underlying
triangulation (V, T ). Then for every component C of G − S there exists a bracing edge
incident with C.
Proof. Let T = (V,E). Since S is a minimal separator in T , the graph T − S (and hence
also G−S) has exactly two connected components C,D. For a contradiction suppose that
there is no bracing edge incident with C. Since T [S] induces a 4-cycle the graph K ob-
tained from the extended component G[C ∪S] of S by adding the edges that connect those
vertex pairs of S which are not adjacent in G, is a 4-connected uni-braced triangulation in
which S induces a K4. Let e be an edge of K incident with C. Then K − e is a minimally
rigid graph on at least five vertices. By Hendrickson’s theorem K − e is not globally rigid.
The fact that G− e can be obtained from K − e by merging K − e and the other extended
component G[D ∪ S] along a complete graph (and, possibly, by deleting edges) implies
that G− e is not globally rigid. This contradiction completes the proof.
The proof shows that the lemma holds even if redundantly globally rigid is weakened to
doubly redundantly rigid in the condition. If the underlying triangulation T is 4-connected,
then every 4-separator of G is obviously a minimal separator in T , so the conditions of
Lemma 5.2 are satisfied.
Let us consider the case when T is not 4-connected and G is doubly braced. Then for
every 3-separator S of T , and corresponding components C,D of T − S, both bracing
edges must connect C and D (for otherwise S is a 3-separator in G − e for some bracing
edge e, contradicting redundant global rigidity). Call a component C arising by the removal
of a 3-separator of T a 3-separator component of T . It is not hard to see that this implies
that T has exactly two minimal 3-separator components C1 and C2, both bracing edges
connect C1 and C2, and that T can be made 4-connected by adding a single edge (from
C1 to C2). We believe that in this rather special case G is redundantly globally rigid.
Otherwise, when T is 4-connected, the necessary condition of Lemma 5.2, together with
Hendrickson’s connectivity condition, might be sufficient.
Conjecture 5.3. Let G = (V,E ∪B) be a doubly braced triangulation. Then G is redun-
dantly globally rigid in R3 if and only if
(i) G− e is 4-connected for all e ∈ E ∪B, and
(a) either T = (V,E) has a 3-separator, or
(b) for every 4-separator S of G and component C of G − S there is a bracing
edge incident with C.
Note that if G is doubly braced and the bracing edges induce two disjoint 4-blocks then
T must be 4-connected. Thus in this case the conjecture can be simplified.
We close this section by noting that an interesting related open problem is to charac-
terize globally rigid block and hole graphs with a single block (with no constraints on the
size of the block and the number of holes - see [2] for the definition). It is possible that the
global rigidity of these graphs can be characterized by Hendrickson’s necessary conditions.
12 Ars Math. Contemp. 24 (2024) #P1.03
Conjecture 5.4. A block and hole graph with a single block is globally rigid in R3 if and
only if it is 4-connected and redundantly rigid in R3 .
A characterization of redundantly rigid block and hole graphs with a single block can
be obtained from a recent result in [5].
ORCID iDs
Siddhant Jajodia https://orcid.org/0009-0008-6644-9851
Tibor Jordán https://orcid.org/0000-0003-3662-5558
Kate Perkins https://orcid.org/0000-0003-3596-7505
References
[1] R. Connelly and W. J. Whiteley, Global rigidity: the effect of coning, Discrete Comput.
Geom. 43 (2010), 717–735, doi:10.1007/s00454-009-9220-0, https://doi.org/10.
1007/s00454-009-9220-0.
[2] J. Cruickshank, D. Kitson and S. C. Power, The generic rigidity of triangulated spheres with
blocks and holes, J. Comb. Theory Ser. B 122 (2017), 550–577, doi:10.1016/j.jctb.2016.08.003,
https://doi.org/10.1016/j.jctb.2016.08.003.
[3] B. Hendrickson, Conditions for unique graph realizations, SIAM J. Comput. 21 (1992), 65–84,
doi:10.1137/0221008, https://doi.org/10.1137/0221008.
[4] B. Jackson and T. Jordán, Graph theoretic techniques in the analysis of uniquely localizable
sensor networks, in: G. Mao and B. Fidan (eds.), Localization Algorithms and Strategies
for Wireless Sensor Networks, pp. 146–173, 2009, doi:10.4018/978-1-60566-396-8.ch006,
https://doi.org/10.4018/978-1-60566-396-8.ch006.
[5] T. Jordán, Rigid block and hole graphs with a single block, Discrete Math. 346 (2023), Pa-
per No. 113268, 7 pp., doi:10.1016/j.disc.2022.113268, https://doi.org/10.1016/
j.disc.2022.113268.
[6] T. Jordán, C. Poston and R. Roach, Extremal families of redundantly rigid graphs in three
dimensions, Discrete Appl. Math. 322 (2022), 448–464, doi:10.1016/j.dam.2022.03.006,
https://doi.org/10.1016/j.dam.2022.03.006.
[7] T. Jordán and S. Tanigawa, Global rigidity of triangulations with braces, J. Comb. Theory Ser.
B 136 (2019), 249–288, doi:10.1016/j.jctb.2018.11.003, https://doi.org/10.1016/
j.jctb.2018.11.003.
[8] T. Jordán and W. Whiteley, Global rigidity, in: J. Goodman, J. O’Rourke and C. Tóth (eds.),
Handbook of Discrete and Computational Geometry, CRC Press, 3rd edition, 2018.
[9] R. Kohta, M. Yamakawa, N. Katoh, Y. Araki, and M. Ohsaki, A design method for optimal
truss structures with certain redundancy based on combinatorial rigidity theory, in: 10th World
Congress on Structural and Multidisciplinary Optimization May 2013, Orlando, Florida, USA,
2013 .
[10] B. Schulze and W. Whiteley, Rigidity and scene analysis, in: J. Goodman, J. O’Rourke and
C. Tóth (eds.), Handbook of Discrete and Computational Geometry, CRC Press, 3rd edition,
2018.
[11] S. Tanigawa, Sufficient conditions for the global rigidity of graphs, J. Comb. Theory Ser. B
113 (2015), 123–140, doi:10.1016/j.jctb.2015.01.003, https://doi.org/10.1016/j.
jctb.2015.01.003.
Q. Chen et al.: Redundantly globally rigid braced triangulations 13
[12] W. Whiteley, Infinitesimally rigid polyhedra. II. Modified spherical frameworks, Trans. Am.
Math. Soc. 306 (1988), 115–139, doi:10.2307/2000832, https://doi.org/10.2307/
2000832.
[13] C. Yu and B. D. O. Anderson, Development of redundant rigidity theory for formation control,
Internat. J. Robust Nonlinear Control 19 (2009), 1427–1446, doi:10.1002/rnc.1386, https:
//doi.org/10.1002/rnc.1386.