Flexing infinite frameworks with applications to braced Penrose tilings
Autoři
Dewar, S.; Legerský, J.
Rok
2023
Publikováno
Discrete Applied Mathematics. 2023, 324 1-17. ISSN 0166-218X.
Typ
Článek
Pracoviště
Anotace
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.
Combinatorics of Bricard's octahedra
Autoři
Gallet, M.; Grasegger, G.; Legerský, J.; Schicho, J.
Rok
2021
Publikováno
Comptes Rendus Mathématique. 2021, 359(1), 7-38. ISSN 1778-3569.
Typ
Článek
Pracoviště
Anotace
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
Autoři
Gallet, M.; Grasegger, G.; Legerský, J.; Schicho, J.
Rok
2021
Publikováno
SIAM Journal on Discrete Mathematics. 2021, 35(1), 325-361. ISSN 0895-4801.
Typ
Článek
Pracoviště
Anotace
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
Autoři
Dewar, S.; Grasegger, G.; Legerský, J.
Rok
2020
Publikováno
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.
Typ
Stať ve sborníku
Pracoviště
Anotace
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
Autoři
Grasegger, G.; Legerský, J.
Rok
2020
Publikováno
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.
Typ
Stať ve sborníku
Pracoviště
Anotace
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
Autoři
Grasegger, G.; Legerský, J.; Schicho, J.
Rok
2020
Publikováno
Journal of Computational Geometry. 2020, 11(1), 548-575. ISSN 1920-180X.
Typ
Článek
Pracoviště
Anotace
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.