Paper Info
Title
Banana spiders: A study of connectivity in 3d combinatorial rigidity
Abstract
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 fle xible 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 com- binatorial rigidity has proved elusive. Little has been pub- lished on the failed attempts. In this paper we show that ver- tex connectivity does not help us in our goal: 3-connectivity together with the 3D extension to Laman's condition is in- sufficient, and 4- and 5-connectivity are neither sufficient nor necessary; a minimally rigid graph cannot be greater than 5- connected. There are many models of rigidity. We examine first- order rigidity of bar-joint frameworks (3, 5). Mathemati- cally, a framework is defined as graph with an embedding in . Once embedded, the edges of the graph become fix ed length bars connected at fle xible joints. Knowing whether a framework is fle xible 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 has a rigid embedding, then almost all embeddings of 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 if there exists an embedding in that gives a rigid framework.) In 1970, Laman published a condition that can be used to test whether a graph is rigid in :
Year
Venue
Keywords
2004
CCCG
two dimensions,three dimensions,first order
Field
DocType
Citations 
Rigidity (psychology),Discrete mathematics,Combinatorics,Structural rigidity,Laman graph,Open problem,Embedding,Vertex (geometry),Graph embedding,Computer science,Complement graph
Conference
3
PageRank 
References 
Authors
0.40
0
2
Name
Order
Citations
PageRank
Andrea Mantler1826.54
Jack Snoeyink22842231.68