In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.
In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.
Rigidity is the property of a structure that it does not bend or flex under an applied force. The opposite of rigidity is flexibility. In structural rigidity theory, structures are formed by collections of objects that are themselves rigid bodies, often assumed to take simple geometric forms such as straight rods (line segments), with pairs of objects connected by flexible hinges. A structure is rigid if it cannot flex; that is, if there is no continuous motion of the structure that preserves the shape of its rigid components and the pattern of their connections at the hinges.
There are two essentially different kinds of rigidity. Finite or macroscopic rigidity means that the structure will not flex, fold, or bend by a positive amount. Infinitesimal rigidity means that the structure will not flex by even an amount that is too small to be detected even in theory. (Technically, that means certain differential equations have no nonzero solutions.) The importance of finite rigidity is obvious, but infinitesimal rigidity is also crucial because infinitesimal flexibility in theory corresponds to real-world minuscule flexing, and consequent deterioration of the structure.
A rigid graph is an embedding of a graph in a Euclidean space which is structurally rigid. [1] That is, a graph is rigid if the structure formed by replacing the edges by rigid rods and the vertices by flexible hinges is rigid. A graph that is not rigid is called flexible. More formally, a graph embedding is flexible if the vertices can be moved continuously, preserving the distances between adjacent vertices, with the result that the distances between some nonadjacent vertices are altered. [2] The latter condition rules out Euclidean congruences such as simple translation and rotation.
It is also possible to consider rigidity problems for graphs in which some edges represent compression elements (able to stretch to a longer length, but not to shrink to a shorter length) while other edges represent tension elements (able to shrink but not stretch). A rigid graph with edges of these types forms a mathematical model of a tensegrity structure.
The fundamental problem is how to predict the rigidity of a structure by theoretical analysis, without having to build it. Key results in this area include the following:
However, in many other simple situations it is not yet always known how to analyze the rigidity of a structure mathematically despite the existence of considerable mathematical theory.
One of the founders of the mathematical theory of structural rigidity was the great physicist James Clerk Maxwell. The late twentieth century saw an efflorescence of the mathematical theory of rigidity, which continues in the twenty-first century.
"[A] theory of the equilibrium and deflections of frameworks subjected to the action of forces is acting on the hardnes of quality... in cases in which the framework ... is strengthened by additional connecting pieces ... in cases of three dimensions, by the regular method of equations of forces, every point would have three equations to determine its equilibrium, so as to give 3s equations between e unknown quantities, if s be the number of points and e the number of connexions[sic]. There are, however, six equations of equilibrium of the system which must be fulfilled necessarily by the forces, on account of the equality of action and reaction in each piece. Hence if e = 3s − 6, the effect of any eternal force will be definite in producing tensions or pressures in the different pieces; but if e > 3s − 6, these forces will be indeterminate...." [5]
The classical mathematical puzzle known as the three utilities problem or sometimes water, gas and electricity asks for non-crossing connections to be drawn between three houses and three utility companies in the plane. When posing it in the early 20th century, Henry Dudeney wrote that it was already an old problem. It is an impossible puzzle: it is not possible to connect all nine lines without crossing. Versions of the problem on nonplanar surfaces such as a torus or Möbius strip, or that allow connections to pass through other houses or utilities, can be solved.
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.
In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is called a planar matroid; these are exactly the graphic matroids formed from planar graphs.
In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.
In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one. Edges of unit distance graphs sometimes cross each other, so they are not always planar; a unit distance graph without crossings is called a matchstick graph.
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.
Jessen's icosahedron, sometimes called Jessen's orthogonal icosahedron, is a non-convex polyhedron with the same numbers of vertices, edges, and faces as the regular icosahedron. It is named for Børge Jessen, who studied it in 1967. In 1971, a family of nonconvex polyhedra including this shape was independently discovered and studied by Adrien Douady under the name six-beakedshaddock; later authors have applied variants of this name more specifically to Jessen's icosahedron.
Ileana Streinu is a Romanian-American computer scientist and mathematician, the Charles N. Clark Professor of Computer Science and Mathematics at Smith College in Massachusetts. She is known for her research in computational geometry, and in particular for her work on kinematics and structural rigidity.
In graph theory, Robbins' theorem, named after Herbert Robbins (1939), states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.
In the mathematics of structural rigidity, a rigidity matroid is a matroid that describes the number of degrees of freedom of an undirected graph with rigid edges of fixed lengths, embedded into Euclidean space. In a rigidity matroid for a graph with n vertices in d-dimensional space, a set of edges that defines a subgraph with k degrees of freedom has matroid rank dn − k. A set of edges is independent if and only if, for every edge in the set, removing the edge would increase the number of degrees of freedom of the remaining subgraph.
In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of representation provide abstract algebraic structures with concrete descriptions in terms of linear algebra.
In geometric graph theory, and the theory of structural rigidity, a parallel redrawing of a graph drawing with straight edges in the Euclidean plane or higher-dimensional Euclidean space is another drawing of the same graph such that all edges of the second drawing are parallel to their corresponding edges in the first drawing. A parallel morph of a graph is a continuous family of drawings, all parallel redrawings of each other.
Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures is an undergraduate-level book on the mathematics of structural rigidity. It was written by Jack E. Graver and published in 2001 by the Mathematical Association of America as volume 25 of the Dolciani Mathematical Expositions book series. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion by undergraduate mathematics libraries.
In the mathematics of structural rigidity, grid bracing is a problem of adding cross bracing to a square grid to make it into a rigid structure. It can be solved optimally by translating it into a problem in graph theory on the connectivity of bipartite graphs.
Strong connectivity augmentation is a computational problem in the mathematical study of graph algorithms, in which the input is a directed graph and the goal of the problem is to add a small number of edges, or a set of edges with small total weight, so that the added edges make the graph into a strongly connected graph.
A sparsity matroid is a mathematical structure that captures how densely a multigraph is populated with edges. To unpack this a little, sparsity is a measure of density of a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms and so it is a graph invariant.
Flattenability in some -dimensional normed vector space is a property of graphs which states that any embedding, or drawing, of the graph in some high dimension can be "flattened" down to live in -dimensions, such that the distances between pairs of points connected by edges are preserved. A graph is -flattenable if every distance constraint system (DCS) with as its constraint graph has a -dimensional framework. Flattenability was first called realizability, but the name was changed to avoid confusion with a graph having some DCS with a -dimensional framework.
In discrete geometry, geometric rigidity is a theory for determining if a geometric constraint system (GCS) has finitely many -dimensional solutions, or frameworks, in some metric space. A framework of a GCS is rigid in -dimensions, for a given if it is an isolated solution of the GCS, factoring out the set of trivial motions, or isometric group, of the metric space, e.g. translations and rotations in Euclidean space. In other words, a rigid framework of a GCS has no nearby framework of the GCS that is reachable via a non-trivial continuous motion of that preserves the constraints of the GCS. Structural rigidity is another theory of rigidity that concerns generic frameworks, i.e., frameworks whose rigidity properties are representative of all frameworks with the same constraint graph. Results in geometric rigidity apply to all frameworks; in particular, to non-generic frameworks.
The Geiringer-Laman theorem gives a combinatorial characterization of generically rigid graphs in -dimensional Euclidean space, with respect to bar-joint frameworks. This theorem was first proved by Hilda Pollaczek-Geiringer in 1927. and later by Gerard Laman in 1970. An efficient algorithm called the Pebble Game is used to identify this class of graphs. This theorem has been the inspiration for many Geiringer-Laman type results for other types of frameworks with generalized Pebble games.