‌‌Evangelos Bartzos (University of Athens) ‌

Algebraic and combinatorial methods for bounding the number of the complex embeddings of minimally rigid graphs Bartzos

We are proposing methods to compute multihomogeneous Bezout bounds (m-Bezout) for counting the number of embeddings of minimally rigid graphs in $\CC^2$ (Laman graphs), $S^2$ and $\CC^3$ (Geiringer graphs) and we also examine their combinatorial aspects. We note that the bounds for Laman graphs in $\CC^2$ coincide with the bounds of their spherical embeddings in $S^2$. We also present computations that indicate that these bounds are tight for certain classes of graphs.

This is joint work with I.Z. Emiris and J. Schicho.

John Bowers (James Madison University)

Inversive Distance Circle Packings and Minkowski Spacetime

Two circle packings are considered congruent if there is a Möbius transformation taking one to the other. The question of uniqueness of inversive distance circle packings was first posed by Bowers and Stephenson in 2006. In 2011 Guo showed that packings of positive genus surfaces are locally rigid and shortly thereafter Luo showed that such packings are globally rigid. The following year, Ma and Schlenker gave a construction of a single counter example to global rigidity for circle packings on the sphere. In understanding why circle packings on the sphere are not unique, we have found it useful to employ techniques from the rigidity theory of Euclidean polyhedra. We have also found the classical characterization of circles on the sphere as vectors in the Minkowski space to be a useful framework for studying circle packings. In this talk we will discuss some of our recent results on the characterization of unique inversive distance circle packings on the sphere and give a brief overview of the connection between circle packings and polyhedra in Minkowski space.

‌‌Bob Connelly (Cornell University)

Rigidity of Sticky Disks Connelly‌

Suppose you have a packing of circular disks in the plane, all of different unrelated radii (generic). The interiors of the disks are disjoint, but some pairs of them can touch (be in contact) on their circular boundaries. If the contacts are to be maintained, i.e. the disks are sticky, when is the configuration rigid? As a function of the number, n, of disks, what is the most number of contacts possible? We will answer these questions together. Please bring some coins to the talk to experiment. This sort of question was motivated by similar questions from granular materials. The following figure shows one such experiment.

This is joint work with Steven Gortler and Louis Theran.

Jim Cruickshank (NUI Galway)

Contact graphs of line segments and arcs in surfaces Cruickshank

The Circle Packing Theorem says that all planar simple graphs arise as the contact graphs of collections of nonoverlapping collections of discs in the plane. It is natural to consider analagous questions for various other classes of geometric objects. We will consider lines, circular arcs and Jordan arcs, but many other classes have been studied. Much of the existing literature on line segments considers the plane case and studies the intersection graphs of various classes of that are distinguished by the type of degeneracies that are allowed at contact points. We are interested in studying analagous problems in higher genus surfaces. In this context, multigraphs arise naturally even for contact graphs of line segments and we propose a definition of contact graph that is better adapted to this situation. We also discuss the natural inductive constructions that arise in this context (and which will be familiar to rigidity people) and survey some of the combinatorial results that we have obtained.

This is joint work with Derek Kitson, Steve Power and Qays Shakir.

‌Dániel Garamvölgyi (Eötvös Loránd University)

Global rigidity of unit ball frameworks Garamvolgyi‌

A d-dimensional framework (G,p) is said to be globally rigid if every d-dimensional framework (G,q) with the same graph and same edge lengths is congruent to (G,p). Global rigidity of frameworks and graphs is a well-studied area of rigidity theory with a number of applications, including the localization problem of sensor networks. Motivated by this application, we consider the new notion of unit ball global rigidity, which can be defined similarly, except that (G,p) as well as (G,q) are required to be unit ball frameworks in the above definition. In a unit ball framework two vertices are adjacent if and only if their distance is less than a fixed constant (which corresponds to the sensing radius in a sensor network). In this talk we highlight some recent results regarding this variant of global rigidity. Among others we identify families of frameworks (and corresponding graphs) in R^d, for all d ≥ 1, which are unit ball globally rigid without being globally rigid in the usual sense. These families contain minimally rigid graphs, too, which have less edges than any of the globally rigid graphs on the same number of vertices.

This is joint work with Tibor Jordán.

Georg Grasegger (RICAM / JKU)

Rigidity and Flexibility on the Sphere

Minimally rigid graphs on the sphere are known to be the Laman graphs. In this talk we present an algorithm for computing the number of realizations of a Laman graph on the sphere. The algorithm itself is purely combinatorial, whereas its proof intrinsically uses algebraic geometry. Using the algorithm we are able to give a similar lower bound for the maximal number of realizations as in the plane. In contrast to the rigid case we also present methods to find non-generic flexible instances for generically rigid graphs on the sphere.

This is joint work with Matteo Gallet, Jan Legersky and Josef Schicho.

Zeyuan He (University of Cambridge)

Flexible Large Quadrilateral Meshes

Consider a surface homomorphic to a disk. A quadrilateral mesh embedded on this surface is generically rigid, but there are still some flexible realizations. Based on a nearly-complete classification of flexible Kokotsakis quadrilaterals from Ivan Izmestiev, here we will present some flexible large quadrilateral meshes with the following additional requirements: (1) All the creases that are not on the boundary are folded (2) The quadrilateral mesh is infinitely extendable in both longitudinal and transverse directions. All the flexible quadrilateral meshes presented here only have one degree of freedom in each branch of their motion.

References:

(a) Izmestiev, I. (2017). Classification of flexible Kokotsakis polyhedra with quadrangular base. International Mathematics Research Notices, 2017(3), 715-808.

(b) Zeyuan He and Simon D. Guest. (2018). On Rigid Origami II: Quadrilateral Creased Papers. arXiv preprint arXiv:1804.06483.

‌Bill Jackson (Queen Mary, University of London)

Global rigidity of linearly constrained frameworks Jackson

A linearly constrained framework in R^d is a point configuration together with a system of constraints which fix the distances between some pairs of points and additionally restricts some of the points to lie in given affine subspaces. It is globally rigid if the con figuration is uniquely de termined by the constraint system, and is rigid if it is uniquely determined within some small open neighbourhood. Streinu and Theran characterised generic rigidity of linearly constrained frameworks in R^2 in 2010. We obtain an analagous characterisation for generic global rigidity in R^2. More precisely we show that a generic linearly constrained framework in R^2 is globally rigid if and only if it is redundantly rigid and `balanced'. We also obtain a stress matrix sufficient condition and a Hendrickson type necessary condition for a generic linearly constrained framework to be globally rigid in R^d.

This is joint work with Hakan Guler and Tony Nixon.

‌Tibor Jordan (Eötvös Loránd University)

Graph reconstruction from unlabeled edge lengths Jordan

In a recent paper Gortler, Thurston, and Theran proved that if every generic framework (G,p) in \R^d is globally rigid for some graph G on n\geq d+2 vertices (where d\geq 2), then already the set of (unlabeled) edge lengths of a generic framework (G,p), together with n, determine the graph as well as the framework up to congruence.

If G is not globally rigid then we cannot expect a conclusion as strong as it is given in their result. In this sense the result is the best possible. Still, there is room for further investigations: the set of edge lengths may be sufficient to uniquely reconstruct the graph G, even if the realization itself is not uniquely determined.

I shall present our new results on this unlabeled reconstruction problem.

This is joint work with Daniel Garamvolgyi.

‌Oleg Karpenkov (University of Liverpool)

Tensegrities and differential forms Karpenkov

In this small talk we show a rather exotic approach to classical statics via differential forms in the next dimension. This leads us to another insight of tensegrities.

Eleftherios Kastis (Lancaster University)

Rigidity on a partially triangulated projective plane

Geometric rigidity has its origins back to 1813 in the study of convex polyhedra (Cauchy). Cruickshank, Kitson and Power gave recently a combinatorial characterization of generic rigidity in three dimensions for the graph of a partially triangulated torus with a single (superficial) hole. In this talk, we shall present similar results for partially triangulated graphs of the real projective plane, namely we show that such a graph is minimally 3-rigid if and only if it is (3,6)-tight. As part of the proof we determine the 8 graphs of this type which are irreducible under edge contractions.

Viktória Kaszanitzky (Budapest University of Technology and Economics)

Rigidity of frameworks in special position

A landmark result of Laman gives a characterisation of rigid generic bar-joint frameworks in the plane. Results that describe various types of rigidity were also established for different classes of frameworks. These, however are of limited use if the framework is not generic. In this talk we review earlier results and new achievements on the rigidity of non-generic frameworks.

‌Derek Kitson (Lancaster University)

Co-boundary operators for infinite frameworks Kitson

In this talk I will give a brief introduction to some basic concepts in operator theory and then present some recent work on a class of infinite matrices in which the matrix entries are determined by an abstract framework. This class includes the incidence matrices of infinite graphs, considered by Mohar and others, and the rigidity matrices of infinite bar-joint frameworks. The questions we consider are: when do these matrices give rise to a bounded operator? Can we compute the operator norm? When are these operators compact? And when are they bounded below?

This is joint work with Lefteris Kastis and Stephen Power.

Peter F. Klemperer (Mount Holyoke College)

Robotic Sensing Applications of Geometric Constraint Systems

Distributed, Multi-Robotic Systems offer solutions for collaborative carrying tasks where the goal object is too large or heavy for any individual robot to bear. Geometric constraint systems offers tools for obtaining movement goals while maintaining multi-robotic formation requirements, but each robot must measure its position using sensors. In this talk, I will discuss a range-bearing sensing approach to localization and discuss applicability to the problem of robot localization with geometric constraint system theory.

‌Jan Legersky (RISC, JKU)

On the Classification of Motions of Laman Graphs Legersky

Laman graphs are known to be minimally rigid in the plane, but they might admit non-generic edge lengths such that there are infinitely many non-congruent vertex-injective realizations. In this talk we present some tools for determing families of such edge lengths. Our methods are based on NAC-colorings, whose existence characterizes the existence of edge lengths with infinitely many non-congruent realizations without the injectivity requirement. We exploit the fact that a subset of active NAC-colorings can be assigned to a particular motion of a graph. We can determine possible active AC-colorings if there are enough 4-cycle subgraphs. Moreover, certain active NAC-colorings impose some algebraic constraints on edge lengths. This allows to give an alternative proof of the result of Walter and Husty stating that the two motions of the complete bipartite graph on 3+3 vertices proposed by Dixon are the only possible ones. Next, we classify the motions of another Laman graph.

This is a joint work with Georg Grasegger and Josef Schicho.

‌András Mihálykó (Eötvös Loránd University)

Co-rigid sets in redundantly rigid augmentations Mihálykó

Let G be a Laman graph (minimally rigid graph in R^2). Suppose that we want to augment G to redundantly rigid graph with the addition of minimum number of edges. This problem was first solved by García and Tejel (2011). However, we take an other route, using the concept of co-rigid sets. A set C is called co-rigid, if G-C is Laman. In this presentation I will talk about the newly discovered properties of co-rigid sets and their application in several problems, including the globally rigid augmentation, minimal cost globally rigid spanning subgraph problem or the pinning number of a Laman graph. Also, I will show some open problems and possible ways to use the concept of co-rigidity to greater extent.

This is joint work with Tibor Jordán and Csaba Király.

Stephen Power (Lancaster University)

Isotopy types of periodic nets and frameworks

We are interested in counting the periodic isotopy types of embedded 3-periodic nets N, both connected ones and entangled ones. Adjacency depth is introduced as a useful taxonomic notion, at least when the quotient graph QG is small. For adjacency depth 1 we determine the 6 disconnected and the 19 connected "lattice nets", that is, those with a 1-vertex QG. Of the 19 there are 9 which appear in the RCSR database, 7 others in the TOPOSpro database, and the remaining 3 are "new" nets, unobserved by chemists.

For natural double-lattice nets, with a 2 vertex QG, there is a small combinatorial explosion. In the connected case with adjacency depth 1 there are 117 underlying structure graphs ("topologies") when the QG is loopless (thus bipartite). These correspond to classes of 1,0,-1 labellings of the QGs. There are 31 topologies which are 6-regular. These in turn give periodic bar-joint frameworks of "Maxwell" type which of interest in rigidity.

This is joint work with the chemists Igor Baburin and Davide Proserpio.

‌Daniel Robertz (University of Plymouth)

The icosahedra of edge length 1 Robertz

Retaining the combinatorial Euclidean structure of a regular icosahedron, namely the 20 equiangular planar triangles, the 30 edges of length 1, and the 12 different vertices together with the incidence structure, we investigate variations of the regular icosahedron admitting self-intersectionsof faces. We determine all rigid equivalence classes of these icosahedra with non-trivial automorphism group and find one curve of flexible icosahedra.

This is joint work with K.-H. Brakhage, A. C. Niemeyer, W. Plesken and A. Strzelczyk. Visualisations and explicit data are available under http://algebra.data.rwth-aachen.de/Icosahedra/visualplusdata.html.

‌Bernd Schulze (Lancaster University)

Group pairings with equivalent rigidity properties for bar-joint and point-hyperplane frameworks Schulze

In this talk we will discuss the effect of symmetry on the infinitesimal rigidity of spherical frameworks and Euclidean bar-joint and point-hyperplane frameworks in general dimension. In particular we show that, under forced or incidental symmetry, infinitesimal rigidity for spherical frameworks with vertices in X on the equator and point-hyperplane frameworks with the vertices in X representing hyperplanes are equivalent. We then show, again under forced or incidental symmetry, that infinitesimal rigidity properties under certain symmetry groups can be paired under inversion on the sphere so that infinitesimal rigidity with a given group is equivalent to infinitesimal rigidity under a paired group. The fundamental basic example is that mirror symmetric rigidity is equivalent to half-turn symmetric rigidity on the 2-sphere. With these results in hand we can deduce some combinatorial consequences for the rigidity of symmetric bar-joint and point-line frameworks.

This is joint work with Katie Clinch, Anthony Nixon and Walter Whiteley.

‌Qays Shakir (NUI Galway)

Finding irreducible (2,2)-tight torus graphs Shakir

In topological graph theory there is an extensive literature around the problem of finding so-called irreducible triangulations and quadrangulations of surfaces. The number of irreducibles tends to grow rapidly as the genus of the underlying surface increases. Motivated by problems in rigidity and in contact geometry, Cruickshank, Kitson, Power and S have considered analogous problems for (2,l)-tight graphs embedded in various surfaces. In recent work, we have shown that there are finitely many (2,2)-tight torus graphs that are irreducible with respect to a certain natural set of topological contraction moves. We were able to show that such irreducibles have at most 8 vertices. That raises the question of determining the set of these irreducibles. There is a finite but large set of (2,2)-tight torus graphs with 8 vertices so in order to find all of these irreducibles we employed a mixture of brute force methods and theoretical insight into the structure of such graphs. We found exactly 116 irreducible graphs.

This is joint work with James Cruickshank.

Audrey St. John (Mount Holyoke College)

Rigidity Theory for Control of Multi-Robot Formations: Challenges and Opportunities

Rigidity theory provides a mathematical framework for the analysis of geometric constraint systems. Motivated by applications such as collective transport, we consider controlling a multi-robot formation through the maintenance of local constraints that preserve the global structure. A leader-follower formation permits control of the entire formation via specified “leader” robots, while “follower” robots autonomously sense and adjust their relative positions to satisfy geometric constraints. In particular, we focus on persistence theory, which can be viewed as a directed analogue of rigidity theory. Modeling a constraint with a directed edge can reduce associated hardware costs by assigning sensing and maintenance to the source. In this talk, we give a brief overview of persistent leader-follower formations before highlighting challenges and opportunities that arise when applying persistence theory to the control of the hardware systems underlying multi-robot formations.

This talk includes joint work with Alyxander Burns, Peter Klemperer, Bernd Schulze and Jaemarie Solyst.

Shin-ichi Tanigawa (University of Tokyo)

Finding auxetic mechanisms

A material with negative poisson ratio is called auxetic in material science. Motivated by this concept, Borcea and Streinu recently introduced the auxeticity for periodic frameworks. In this talk I will explain an experimental study for finding auxetic mechanisms based on Borcea-Streinu’s result. (Joint work with Kazuki Ishihama)

Louis Theran (University of St Andrews)

Efficient algorithms for unlabelled graph realisation in dimension one

A recent result of Gortler-Theran-Thurston says that if G is a generically globally rigid graph in dimension d and (G, p) is a generic d-dimensional framework, then it is possible to recover G and p from the set of unlabelled edge length measurements from (G, p). The algorithmic “unlabelled distance geometry” problem of actually finding G and p from these unlabelled measurements is not easier than the labelled variant, which is already NP-hard. Aside from the very special case of unlabelled trilateration, this problem is largely unexplored. I’ll talk about an algorithm for unlabelled distance geometry in dimension one that works on all 3-connected graphs. This algorithm works with rational inputs and, with sufficient precision, is robust to noise.

This is joint work with Bob Connelly and Shlomo Gortler.

‌Daniel Zelazo (Technion - Israel Institute of Technology)

Rigidity Theory in Multi-Agent Coordination: A Fundamental System Architecture Zelazo

The implementation of coordination and control algorithms for multi-agent systems often depends explicitly on the sensing modalities available to the systems. Common coordination goals, such as formation control, can have vastly different control algorithms depending on what information is available to each robot. In this talk, we explore how various sensing modalities, such as distance measurements or bearing measurements, are used to achieve coordination tasks like formation control and localization. Despite the differences of the sensing modalities, we show that they share a common underlying conceptual and theoretical framework based on rigidity theory. In fact, notions from rigidity theory provide an understanding of what the correct system architectures for multi-agent systems are. This talk will highlight recent results in this area related to formation control and sensor localization.