Banana Spiders: A Study of Connectivity in 3D Combinatorial Rigidity

Ў

Andrea Mantler

Jack Snoeyink

ў¤Ј¦ҐЁ§Ё©§ Finding a combinatorial test for rigidity in 3D is an open problem. We prove that vertex connectivity cannot be used to construct such a test by describing a class of mechanisms that increase the vertex connectivity of flexible graphs to 5. Our result is tight, as minimally rigid graphs in 3D can be at most 5-connected. §©!#"%$&'§() In two dimensions, combinatorial rigidity is well understood: Laman's condition on the number and distribution of edges is both necessary and sufficient for determining if a framework is rigid. In three dimensions, however, finding a test for combinatorial rigidity has proved elusive. Little has been published on the failed attempts. In this paper we show that vertex connectivity does not help us in our goal: 3-connectivity together with the 3D extension to Laman's condition is insufficient, and 4- and 5-connectivity are neither sufficient nor necessary; a minimally rigid graph cannot be greater than 5connected. There are many models of rigidity. We examine firstorder rigidity of bar-joint frameworks [3, 5]. Mathematically, a framework is defined as graph with an embedding in 021 . Once embedded, the edges of the graph become fixed length bars connected at flexible joints. Knowing whether a framework is flexible or rigid, i.e. whether or not there exists an edge-length preserving deformation that changes the distances between some non-adjacent vertices, is useful in many applications, such as designing bridges and other structures. If A graph 3 has a rigid embedding, then almost all embeddings of 3 produces a rigid framework. Thus we would like to assume a generic embedding (see [3, 5]), and determine whether or not a framework is rigid based solely on the graph of vertices and edges. (We call a graph rigid in 021 if there exists an embedding in 041 that gives a rigid framework.) In 1970, Laman published a condition that can be used to test whether a graph is rigid in 065 : Condition 1 (Laman, [3, 4]) A graph [email protected] is rigid for dimension 2 if and only if there is a subset EPI of E such that: Q Department of computer science, University of North Carolina at RChapel Hill, [email protected] Department of Computer Science, University of North Carolina at Chapel Hill, [email protected]

S T Figure 1: The double banana, with an implied hinge edge through U and V . 1. W EHIXWY7a`bW AcW'dfe , and 2. for all EgI IihpEHI where W AP9qErI IGsW#tu` , we have W EHI IXW#v `bW Aw9qErI IGsW'dfe . This condition, known as Laman's condition, is both nec- essary and sufficient. Note that the graph 3PIx7y9qAiCErIG is minimally rigid: removing any edge from 3I gives a flexi- ble graph. Embedded generically, a minimally rigid graph produces an isostatic framework [5]. Modifying Laman's condition for 3D, we get: Condition 2 ([3]) A graph [email protected] is rigid for dimension 3 if and only if there is a subset EwI of E such that: 1. W E I WY7e%W AcW'df , and 2. for all EgI IihpEHI where W AP9qErI IGsW#te , we have W EHI IXW#v e%W Aw9qErI IGsW'df . We refer to Condition 2 as Laman's condition, and call graphs satisfying this condition Laman graphs. Although Laman's condition is necessary, it is no longer sufficient. The double banana [2], shown in Figure 1, is the classic example of a framework that satisfies Laman's condition, yet is flexible. The double banana is the smallest example where Laman's condition is insufficient, but what are others? Lacking a necessary and sufficient extension of Laman's condition to 3D, we would at least like to characterize the cases where Laman's condition is not sufficient. A natural question is whether triangles are required for rigidity. Euler's formula shows that planar graphs require at least one triangle to be rigid in 2D, and must be fully trian- gulated to be rigid in 3D. The bipartite graph s , however, was known in the 19th century to be infinitesimally rigid in 2D. Bolker and Roth [1] proved that triangles are also not

44

CCCG 2004, Montreal, Quebec, August 911, 2004

necessary for rigidity for non-planar graphs in 3D: bipartite graphs c and c are generically rigid in 3D, as are all bipartite graphs ¤ where Cdtfe . In this paper we extend the double banana counterexample to show that vertex connectivity together with Laman's condition is neither a necessary nor a sufficient condition for rigidity in three dimensions. In the double banana, there is an implied hinge through vertices U and V . A hinge is an edge, gihkjrlmE , around which two or more rigid components can rotate. An implied hinge, gbh)jolmn E , consists of a pair of vertices, p¦h and p'j , whose distance is implied by two or more disjoint (except in p#h and p'j ) maximal rigid components. The line through p h and p j acts as the hinge pin around which the attached rigid components rotate. The double banana is a 2-vertex-connected graph. A graph is q -vertex-connected (or q -connected) if there exist q ver- tices such that removing these vertices disconnect the graph, but no set of qrdfs vertices disconnect the graph. A natural, but false, conjecture is that graphs with implied hinges are at most 2-connected. We add mechanisms (spiders) to increase the connectivity of any graph with an implied hinge. t uwvxvby ©{zib$ "m m| x}y '§( ~()§

To begin, we observe that minimally rigid graphs cannot have 6-vertex connectivity or higher.

Theorem 1 A minimal graph, 379qAiCEHG , that satisfies Laman's condition is at most 5-connected.

PaebnWrAPdooWFtfhdo.usV,ewW EcrteeWxg7edteqg5 revaes9qbinW AcaWFq d- cs9op¦`[email protected] APcteWq,daW AcgnrdWantp`hh.uasSr3einacistelaeWtEamstWoq 7s,t

5-connected.

We are interested, therefore, in the possibility of 3-, 4- and 5-connected flexible graphs. ў F| x}y '§ y "b yY (Ј& y ©! vb

Figure 2(a) from Whiteley's survey [5] illustrates the sim-

plest spider that converts the 2-connected double banana to

a 3-connected flexible graph. This spider consists of a sin- gle vertex, p , connected by three edges (legs) to the two

bananas. Notice that we do not connect the legs to the im-

plied hinge vertices. As the bananas rotate, p 5 move closer or farther apart, causing pb

vertices p to swing

and up or

down.

Lemma 2 The graph 379qAiCEHG in Figure 2(a) is a 3- connected, flexible Laman graph.

Proof. The reader can check that the graph 3 is 3- connected, as it has no cut set of size two, and that it satis- fies Laman's condition, as adding one vertex and three edges

maintains W EWv ebW AcW&dЎ for all induced subgraphs, with

equality for the full graph.

Adding the basic spider adds one vertex and three edges, maintaining the equation W EW7ebW APWYd by adding three to

each side. No subgraph violates part 2 of Laman's condition, thus, 3 continues to satisfy Laman's condition.

To verify the graph is still flexible, we look at the space of

infinitesimal motions, which is a linear subspace. Adding an

edge adds a single linear constraint, reducing the dimension

of the subspace by 1. The space of motions of a graph with

a hinge plus the spider body has dimension at least 10: 3 for

the Euclidean degrees of freedom for the spider body vertex,

6 for the Euclidean degrees of freedom for the graph, and one

for the flexibility at the hinge. Adding the three spider legs

reduces the dimension to 7. Thus, there is one internal degree

of freedom, and the graph with the spider is flexible.

We now move on to flexible graphs with higher connectivity. ў ўЈў F| x}y '§ y "% yY (Ј& ym ©! vb

Figure 2(b) shows an example of a 4-connected flexible graph that satisfies Laman's condition. In this graph, we have a spider with a triangular body, and six legs connecting the spider body to the double banana. Notice that we have the spider legs connecting to non-hinge vertices, three legs per banana, with the legs for each banana terminating in two vertices.

Lemma 3 The graph 379qAiCEHG in Figure 2(b) is a 4- connected, flexible Laman graph.

Proof. As in the proof of Lemma 2, observe 3 with the spider, 3H¤ , removed: 3rҐi7a3od{3r¤ is the two-connected double banana shown in Figure 1. The set ¦U%CFVЁ§6h©A is the only cut set of size two of 3 Ґ , and there are no cut sets of size three. Adding the spider back to 3 Ґ , we see that the set ¦ЁUbCЄV§{h A no longer forms a cut set, and we must remove another two vertices in order to disconnect 3 . Additionally, we cannot disconnect any component of 3 ¤ from 3 without removing at least four vertices. Graph 3 is 4-connected. Adding 3 ¤ adds three vertices and nine edges, maintaining the equation W EcWY7aebW APWЄd by adding nine to each side. No subgraph violates part 2 of Laman's condition, thus, 3

continues to satisfy Laman's condition. The space of motions for 3PҐ plus a triangle (the spider

body) has dimension 13, since a triangle has 6 Euclidean

degrees of freedom. Adding the six legs reduces the dimen-

sion to 7, and again the graph with the spider remains flexi-

ble.

« ўЈ« F| x}y '§ y "% yY (Ј& ym ©! vb

Figure 2(c) illustrates an example of a 5-connected flexible graph that satisfies Laman's condition. In this graph, the spider body has grown to 6 vertices, and forms a minimally rigid

45

16th Canadian Conference on Computational Geometry, 2004

(a)

(b)

(c)

v1 v2 v0

Figure 2: The double banana with spiders increasing the vertex connectivity to (a) 3-connectivity, (b) 4-connectivity, and (c) 5-connectivity. Spider legs are drawn as dashed lines.

graph. Notice that within the body, each vertex has degree 4. We add one leg to each spider body vertex, increasing the degree of each body vertex to 5. Three legs connect to each banana of the double banana, and each leg terminates at a distinct, non-hinge vertex. Lemma 4 The graph 3¬7¬9BADCFEHG in Figure 2(c) is a 5- connected, flexible Laman graph. The proof of Lemma 4 is basically the same as that of Lemma 3. z y ' "zi Ґ

In this section we give a method to increase the connectivity of a graph, 387®9BADCFEHG , without decreasing the flexibility,

or causing Laman's condition to be violated. To increase

the connectivity, we add copies of the 5-spider described in

Section 5.

Let AЇ7y¦p'Cs°s°°sCp spiders, with spider

І

}± § be the having feet

vertices p h Cs°°s°Cdp

of hґі

3

,

. We add where the

indices are taken modulo . We will now prove that this

graph, 3H , consisting of 3 plus spiders, is 5-connected.

That is, that there are no bad cut sets, which are cut sets with

fewer than five vertices.

Lemma 5 Any graph 3 can be embedded as a vertexinduced subgraph of a 5-vertex-connected graph 3m®7 9qAbCEwG .

Proof. Because every vertex has degree at least five, no bad

cut set can isolate a single vertex.

If there is a bad cut set, Aµ , containing a spider body ver-

tex, p ¤ , then there is a bad cut set Awµ I that includes vertices

only from A . Cut that AHµ I 7uA%µd¶¦p

set Aµ splits Ax into ¤ §2·¦pYё&§ is also a

A and bad cut

A 5. set,

We prove where p}ё

is the foot vertex adjacent to p ¤ . This results in a cut set with

one fewer spider body vertices. By induction, we can find a Arµ I that contains vertices only from A . Besides p ё , the only neighbours of p%¤ are four spider body

vertices, since we always connect new spiders to vertices of

3. and A 5.

TTA hh5 eu, sss,ipnwicd.ele.orth.bgeo.n,dp&ythё neireseiginwhboA ou ul,drthsbeoesfepp№did¤geecrsabncoondonytnenbceetiiginnhgbboA out hrsaAnodf

pY¤ are in A 5 and A µ , and moving p ё to A µ and p¤ to A 5 results in a valid bad cut set. Finally, we prove that a bad cut set APµ I hfA does not exist: we can remove up to four vertices and still have a cycle, є , that visits every remaining vertex p h lA . Note that a spider connects vertices p h Cs°s°°sCp h»і . Thus,

using spider edges, we can walk forward through the vertices in A , taking "step sizes" of up to five. We construct є by

taking the next smallest available step forward, which will

be to the next p h ln A µ I . The cut set, A µ I , cannot block this

path, since W Agµ I W}јЎe .

We now prove that adding the 5-spiders to 3 does not cause Laman's condition to be violated, or decrease the flex- ibility of 3 .

Lemma 6 If a graph 3Ѕ[email protected] satisfies Laman's condition, 3 plus a 5-spider 3 ¤ satisfies Laman's condition.

Proof. We examine all subgraphs of 3ѕ3¤ to verify that part 2 of Laman's condition holds. We know that all sub- graphs of 3 satisfy part 2, and can easily verify that subgraphs of 3r¤ satisfy part 2. Consider an induced subgraph on ї , a subset of the spider body vertices, and AАhБA . If W їwW}t¶e and W A I W}tЎe , we know:

W EP9BїDGsWВv ebW їwWЁdf&C W EP9qAgGsWВv ebW AcW'dxC

and hence, W EP9qїiGsW·W EP9qAgGsW}vfex9FW їwW·aW AcW GГdЎs`¦°

Since there are no more than six spider legs connecting the vertices in ї and A , the subgraph satisfies part 2. Cases where W їwW2ј@e or W AcWwјДe also satisfy part 2 of Laman's

condition: we either add one vertex and up to two edges, or

two vertices and up to five edges; either way, the inequality

of part 2 holds.

Lemma 7 Adding a 5-spider, 3 ¤ , to a graph 3 cannot de- crease the space of infinitesimal motions.

Proof. We sketch the proof, using the terminology of Whiteley's survey [5] and Graver et al. [3].

46

CCCG 2004, Montreal, Quebec, August 911, 2004

Given a generic embedding of 3 , an infinitesimal motion of 3 is an assignment of "velocities" to the embedded vertices of 3 such that ЕЖ p&hИI ЗЙ 7К , where Е is the rigidity ma- trix determined by the coordinates of the vertices. Each row in Е represents an edge in 3 , and each column represents a coordinate of a vertex in 3 . Let 34I%73gѕi3 ¤ , and let the rigidity matrices of 3 , 3wI , the spider body, and the spider legs be Е , ЕcI , Е Ґ , and Ж Е{Лbё&Е6Л Ґ З , respectively. Then ЕgI can be decomposed into: МН Е К ОП Е I 7 К Е6Ґ Е Лxё Е Л Ґ

We know ЕЖ p¦hI ЗЙ 7К , and thus we need only find a solution

to:

Р

ЕҐ Е¤Л ҐcС

Ж p ҐBI h З Й

7

РК dwЕ6Лxё&Ж phI ЗЙ

С

where Ж p¦ҐBI h З are the velocities of the spider body vertices. We know the rank of the above rigidity matrix is less than or

equal to 18 since there are only 18 rows: 12 for the spider

body edges, and 6 for the legs. Thus, there will be at least one

valid assignment for the DТwe for every valid infinitesimal

coordinates motion of 3 ,

of Ж pҐBI h there

З . Therefore, exists a valid

infinitesimal motion of 3 ¤ .

Theorem 8 Any graph, 3 , can be embedded as a vertexinduced subgraph of a 5-vertex-connected graph, 3 , such that the space of infinitesimal motions is the same or larger, and 3 satisfies Laman's condition if 3 does.

Proof. By Lemma 5, we can use 5-spiders to increase the vertex connectivity of 3 to five. By Lemma 7, adding a 5-

spider does not decrease the internal degrees of freedom of

3 , and 3r retains the flexibility of 3 . By Lemma 6, 3P

satisfies Laman's condition if 3 does.

У | Y$}Ґs(k Ґ

Ш ўxЩ Ъ6 y "&Ы y¦Чwy¦ §ЄҐ Thanks to Walter Whiteley for helpful discussions and advice. This research has been partially supported by NSF ITR grant 0086013. Ь yЭXy © y¦ y Ґ [1] E. Bolker and B. Roth. When is a bipartite graph a rigid framework? PACIFIC JOURNAL OF MATHEMATICS, 90(1):2744, 1980. [2] H. Crapo. structural rigidity. Structural Topology, 1:2645, 1979. [3] J. Graver, B. Servatius, and H. Servatius. Combinatorial Rigidity. Graduate studies in Math., AMS, 1993. [4] G. Laman. On graphs and rigidity of plane skeletal structures. J. Eng. Mathematics, 4:331340, 1970. [5] W. Whiteley. Rigidity and scene analysis. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 60, pages 1327--1354. Chapman & Hall/CRC Press, Boca Raton, FL, 2nd Edition, 2004.

As we have shown in Sections 3, 4 and 5, we can increase the vertex connectivity of the double banana graph using spiders. In Section 6, we prove that any flexible graph satisfying Laman's condition is an induced subgraph of a 5-connected, flexible graph satisfying Laman's condition. Thus, we cannot use connectivity to create a necessary and sufficient test for combinatorial rigidity in 3D. Ф ХHvby}fЦ ©!bЈx y}Ч Ґ

Problem 1 Are the graphs in Figures 2(a) through (c) the smallest 3-, 4-, and 5-connected counterexamples to the sufficiency of Laman's condition? Problem 2 Find a necessary and sufficient extension of Laman's condition to 3D.

47

Intelligent agents for the synthetic battlefield: A company of rotary wing aircraft, 7 pages, 0.03 Mb

doc.uments.com

About Us :: Privacy Policies :: Terms of Service :: Feedback :: Copyright :: Contact Us :: DMCA Policy

Copyright © 2018 doc.uments.com