Coupler curves of graphs in the plane and counting realizations

Home

Table of contents

Introduction

The mechanical engineer James Watt invented in 1784, for his steam engine, a linkage that converts a rotary motion into an approximate straight line motion. It took 80 years before Peaucellier and Lipkin realized in 1864 that there exists a linkage that draws a straight line segment exactly. The Kempe's universality theorem from 1876 states that any algebraic curve segment is drawn by some linkage.

Watt's linkage Peaucellierā€“Lipkin linkage
Picture Picture
Source: Wikipedia: Arglin Kampling (CC BY-SA 4.0)

Let us consider linkages as realizations of graphs in the plane for some given edge lengths. The graphs are flexible as we consider the vertices as revolute joints. The curve segments that are drawn by a vertex are segments of algebraic curves that are known as coupler curves.

Picture
Source: wiki.wpi.edu: Rmwiesenberg

Our goal is to determine for a given flexible graph the degree and genus of its coupler curve for some random choice of edge lengths. A closely related problem is to efficiently determine invariants of rigid graphs.

Intersections of coupler curves

Before we can state our main result, we need to introduce, at least informally, some concepts.

Let G=(V,E) be a graph with vertices V and edge E such that 0 is a vertex in V and {1,2} is an edge in E.

The edge lengths w is a function that assigns to each edge e in E a positive real number w(e) such that w({1,2})=1.

A realization of G that is compatible with edge lengths w, assigns to each vertex i in V a point (xi,yi) in the complex plane, such that

We call G a calligraph if it admits a one dimensional set of realizations for almost all choices of edge lengths w. The coupler curve of a calligraph G for some edge lengths w, consists of all w-compatible realizations of the vertex 0 into the complex plane.

For example, the real points in the coupler curves of the calligraphs C and L consists of two circles and one circles, respectively. The radii and centers of the circles are determined by the choice of edge lengths.

Picture

The number of realizations of G is the same for almost all edge lengths and denoted by c(G). If c(G) is finite and at least one, then G is a minimally rigid graph.

For example, the union C ⋃ L of the calligraphs C and L is minimally rigid. The number of realizations c(C ⋃ L) equals four and corresponds to the number of intersections between the coupler curves:

Picture

We call (G,G') a calligraphic split if G and G' are calligraphs and their union is a minimally rigid graph with |V|+|V'|-3 vertices and |E|+|E'|-1 edges.

For example, (C,L) is a calligraphic split for C ⋃ L.

A theorem by Hilda Pollaczek-Geiringer (1927) and Gerard Laman (1970) characterizes minimally rigid graphs in combinatorial terms:

From this we obtain a combinatorial characterization of calligraphs:

Classes of calligraphs and counting realizations

A class for calligraphs is a function that assigns to each calligraph G a triple [G] of integers such that the following two axioms are fulfilled:

Theorem. ([2]) The class for calligraphs exists and is unique.

We can compute the number of realizations c(G ⋃ G') using the combinatorial algorithm of [1]. Hence, we can compute classes of calligraphs combinatorially.

For example, let L, R and C be the calligraphs in axiom A1 and let H be the calligraph illustrated below.

Picture

The algorithm of [1] gives

Hence, by axioms A1 and A2 we obtain

We solve this linear system of equations for (a,b,c) and find that

As an application of the theorem, we obtain an improved algorithm for computing the number of realizations of minimally rigid graphs as follows.

By axiom A2, the computation of c(G ⋃ G') is equivalent to the computation of the classes [G] and [G']. By axioms A1 and A2, the computation of [G] and [G'] is equivalent to computing the numbers of realizations of the following 6 minimally rigid graphs:

If G and G' each have at least 5 vertices, then each of the above 6 graphs has strictly less vertices than G ⋃ G'. In this case, experiments with the algorithm of [1] suggest that it is faster to compute the numbers of realizations of these 6 graphs, than to compute the number of realizations of the single graph G ⋃ G'.

We refer to [2, Remarks 4 and 5] for more details.

Bounds on the degrees and genera of coupler curves

In order to recover from the class of a calligraph, bounds on the degrees and genera of the irreducible components of its coupler curve, we need to introduce a notion of multiplicity.

Suppose that G is a calligraph and let T be its coupler curve for some general choice of edge lengths w. Let p be a general point on T. The coupler multiplicity of G is defined as the number of w-compatible realizations that send vertex 0 to the point p.

For example, the right calligraph below with edge lengths w has coupler multiplicity 2, since a w-compatible realization that sends vertex 0 to p, sends vertices 1, 2 and 3 to the points (0,0), (1,0) and q, respectively, where q lies either above or below the point (1,0).

Picture

The following combinatorial condition is useful for determining the coupler multiplicity of a calligraph G=(V,E) in terms of the graph G'=(V,E ⋃ {{1,0},{2,0}}):

We are now ready to relate classes of calligraphs to the degrees and geometric genera of components of their coupler curves.

Theorem. ([2]) Suppose that G is a calligraph with class [G]=(a,b,c) and coupler multiplicity m. If T1,...,Tn are the n irreducible components of the coupler curve T of G for some general choice of edge lengths, then there exists n integer triples (a1,b1,c1),...,(an,bn,cn) such that the following holds for all i in {1,...,n}:

where deg(Ti), g(Ti) and |Sing Ti| denotes the degree, geometric genus and number of singularities of Ti, respectively.

As a corollary we obtain

We conjecture that (a1,b1,c1)=...=(an,bn,cn) and that g(T1)=...=g(Tn) is equal to the upper bound.

For example, let us consider the calligraph H and recall that [H]=(6,2,2). It follows from the above combinatorial condition that H has coupler multiplicity 1. We illustrated its coupler curve T for some general choice of edge lengths.

Picture

We deduce from this approximate rendering that T consist of two irreducible components T1 and T2 such that

By instantiating the above theorem for all possible choices for (a1,b1,c1) and (a2,b2,c2), we find as only possibility that

Therefore, it follows that

As a second example, we consider the calligraph F below with class [F]=(272,0,0). Using our combinatorial condition we verify that F has coupler multiplicity 1. Thus for almost all choices of edge lengths, the coupler curve of F has degree 2∙272=544.

Picture

We show in [2, Section 3.3] that the coupler curve of F has at least 16 irreducible components that each has degree at most 34 and geometric genus at most 256.

An open problem is to find the exact values for the degrees and geometric genera of each irreducible component of a coupler curve of a calligraph for some general choice of edge lengths.

References

[1] The number of realizations of a Laman graph,
J. Capco, M. Gallet, G. Grasegger, C. Koutschan, N. Lubbes, J. Schicho,
SIAM Journal on Applied Algebra and Geometry, 2018,
[journal], [arxiv], [html]
[2] Coupler curves of moving graphs and counting realizations of rigid graphs,
G. Grasegger, B. El Hilany, N. Lubbes, 2022, preprint,
[arxiv], [code]

This research was funded by FWF project P33003.

Top