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 |

Authors (2 rows)

Cited by (3 rows)

References (0 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Andrea Mantler | 1 | 82 | 6.54 |

Jack Snoeyink | 2 | 2842 | 231.68 |