Flexibility and rigidity of frameworks consisting of triangles and parallelograms
Authors
Grasegger, G.; Legerský, J.
Year
2024
Published
Computational Geometry: Theory and Applications. 2024, 120 ISSN 0925-7721.
Type
Article
Departments
Annotation
A framework, which is a (possibly infinite) graph with a realization of its vertices in the plane, is called flexible if it can be continuously deformed while preserving the edge lengths. We focus on flexibility of frameworks in which 4-cycles form parallelograms. For the class of frameworks considered in this paper (allowing triangles), we prove that the following are equivalent: flexibility, infinitesimal flexibility, the existence of at least two classes of an equivalence relation based on 3- and 4-cycles and being a non -trivial subgraph of the Cartesian product of graphs. We study the algorithmic aspects and the rotationally symmetric version of the problem. The results are illustrated on frameworks obtained from tessellations by regular polygons.
Flexing infinite frameworks with applications to braced Penrose tilings
Authors
Dewar, S.; Legerský, J.
Year
2023
Published
Discrete Applied Mathematics. 2023, 324 1-17. ISSN 0166-218X.
Type
Article
Departments
Annotation
A planar framework – a graph together with a map of its vertices to the plane – is flexible if it allows a continuous deformation preserving the distances between adjacent vertices. Extending a recent previous result, we prove that a connected graph with a countable vertex set can be realized as a flexible framework if and only if it has a so-called NAC-coloring. The tools developed to prove this result are then applied to frameworks where every 4-cycle is a parallelogram, and countably infinite graphs with n-fold rotational symmetry. With this, we determine a simple combinatorial characterization that determines whether the 1-skeleton of a Penrose rhombus tiling with a given set of braced rhombi will have a flexible motion, and also whether the motion will preserve 5-fold rotational symmetry.
Bracing frameworks consisting of parallelograms
Authors
Grasegger, G.; Legerský, J.
Year
2022
Published
The Art of Discrete and Applied Mathematics. 2022, 5(2), 1-21. ISSN 2590-9770.
Type
Article
Departments
Annotation
A rectangle in the plane can be continuously deformed preserving its edge lengths, but adding a diagonal brace prevents such a deformation. Bolker and Crapo characterized combinatorially which choices of braces make a grid of squares infinitesimally rigid using a bracing graph: a bipartite graph whose vertices are the columns and rows of the grid, and a row and column are adjacent if and only if they meet at a braced square. Duarte and Francis generalized the notion of the bracing graph to rhombic carpets, proved that the connectivity of the bracing graph implies rigidity and stated the other implication without proof. Nagy Kem gives the equivalence in the infinitesimal setting. We consider continuous deformations of braced frameworks consisting of a graph from a more general class and its placement in the plane such that every 4-cycle forms a parallelogram. We show that rigidity of such a braced framework is equivalent to the non-existence of a special edge coloring, which is in turn equivalent to the corresponding bracing graph being connected.
Flexible Placements of Graphs with Rotational Symmetry
Authors
Dewar, S.; Grasegger, G.; Legerský, J.
Year
2022
Published
2nd IMA Conference on Mathematics of Robotics. Cham: Springer, 2022. p. 89-97. Springer Proceedings in Advanced Robotics. vol. 21. ISSN 2511-1256. ISBN 978-3-030-91351-9.
Type
Proceedings paper
Departments
Annotation
We study the existence of an n-fold rotationally symmetric placement of a symmetric graph in the plane allowing a continuous deformation that preserves the symmetry and the distances between adjacent vertices. We show that such a flexible placement exists if and only if the graph has a NAC-colouring satisfying an additional property on the symmetry; a NAC-colouring is a surjective edge colouring by two colours such that every cycle is either monochromatic, or there are at least two edges of each colour.
Zero-Sum Cycles in Flexible Non-triangular Polyhedra
Authors
Gallet, M.; Grasegger, G.; Legerský, J.; Schicho, J.
Year
2022
Published
2nd IMA Conference on Mathematics of Robotics. Cham: Springer, 2022. p. 137-143. Springer Proceedings in Advanced Robotics. vol. 21. ISSN 2511-1256. ISBN 978-3-030-91351-9.
Type
Proceedings paper
Departments
Annotation
Finding necessary conditions for the geometry of flexible polyhedra is a classical problem that has received attention also in recent times. For flexible polyhedra with triangular faces, we showed in a previous work the existence of cycles with a sign assignment for their edges, such that the signed sum of the edge lengths along the cycle is zero. In this work, we extend this result to flexible non-triangular polyhedra.
Zero-sum cycles in flexible polyhedra
Authors
Gallet, M.; Grasegger, G.; Legerský, J.; Schicho, J.
Year
2022
Published
Bulletin of the London Mathematical Society. 2022, 54(1), 112-125. ISSN 0024-6093.
Type
Article
Departments
Annotation
We show that if a polyhedron in the three-dimensional affine space with triangular faces is flexible, that is, can be continuously deformed preserving the shape of its faces, then there is a cycle of edges whose lengths sum up to zero once suitably weighted by 1 and -1 . We do this via elementary combinatorial considerations, made possible by a well-known compactification of the three-dimensional affine space as a quadric in the four-dimensional projective space. The compactification is related to the Euclidean metric, and allows us to use a simple degeneration technique that reduces the problem to its one-dimensional analog, which is trivial to solve.
Combinatorics of Bricard's octahedra
Authors
Gallet, M.; Grasegger, G.; Legerský, J.; Schicho, J.
Year
2021
Published
Comptes Rendus Mathématique. 2021, 359(1), 7-38. ISSN 1778-3569.
Type
Article
Departments
Annotation
We re-prove the classification of motions of an octahedron - obtained by Bricard at the beginning of the XX century - by means of combinatorial objects satisfying some elementary rules. The explanations of these rules rely on the use of a well-known creation of modern algebraic geometry, the moduli space of stable rational curves with marked points, for die description of configurations of graphs on the sphere. Once one accepts the objects and the rules, the classification becomes elementary (though not trivial) and can be enjoyed without the need of a very deep background on the topic.
On the existence of paradoxical motions of generically rigid graphs on the sphere
Authors
Gallet, M.; Grasegger, G.; Legerský, J.; Schicho, J.
Year
2021
Published
SIAM Journal on Discrete Mathematics. 2021, 35(1), 325-361. ISSN 0895-4801.
Type
Article
Departments
Annotation
We interpret realizations of a graph on the sphere up to rotations as elements of a moduli space of curves of genus zero. We focus on those graphs that admit an assignment of edge lengths on the sphere resulting in a flexible object. Our interpretation of realizations allows us to provide a combinatorial characterization of these graphs in terms of the existence of particular colorings of the edges. Moreover, we determine necessary relations for flexibility between the spherical lengths of the edges. We conclude by classifying all possible motions on the sphere of the complete bipartite graph with 3+3 vertices where no two vertices coincide or are antipodal.
Computing Animations of Linkages with Rotational Symmetry
Authors
Dewar, S.; Grasegger, G.; Legerský, J.
Year
2020
Published
36th International Symposium on Computational Geometry (SoCG 2020). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. Leibniz International Proceedings in Informatics (LIPIcs). vol. 164. ISSN 1868-8969. ISBN 978-3-95977-143-6.
Type
Proceedings paper
Departments
Annotation
We present a piece of software for computing animations of linkages with rotational symmetry in the plane. We construct these linkages from an algorithm that utilises a special type of edge colouring to embed graphs with rotational symmetry.
FlexRiLoG—A SageMath Package for Motions of Graphs
Authors
Grasegger, G.; Legerský, J.
Year
2020
Published
Mathematical Software – ICMS 2020. Springer, Cham, 2020. p. 442-450. Lecture Notes in Computer Science. vol. 12097. ISSN 0302-9743. ISBN 978-3-030-52199-8.
Type
Proceedings paper
Departments
Annotation
In this paper we present the SageMath package FlexRiLoG (short for flexible and rigid labelings of graphs). Based on recent results the software generates motions of graphs using special edge colorings. The package computes and illustrates the colorings and the motions. We present the structure and usage of the package.
On the Classification of Motions of Paradoxically Movable Graphs
Authors
Grasegger, G.; Legerský, J.; Schicho, J.
Year
2020
Published
Journal of Computational Geometry. 2020, 11(1), 548-575. ISSN 1920-180X.
Type
Article
Departments
Annotation
Edge lengths of a graph are called flexible if there exist infinitely many non-congruent realizations of the graph in the plane satisfying these edge lengths. It has been shown recently that a graph has flexible edge lengths if and only if the graph has a special type of edge coloring called NAC-coloring. We address the question how to determine paradoxical motions of a generically rigid graph, namely, proper flexible edge lengths of the graph. We do so using the set of all NAC-colorings of the graph and restrictions to 4-cycle subgraphs.