Finding Optimal Paths in Beadworks: What If Euler Were a Beader?

Year: 2013 Authors: Ron Asherov

Core claim

Regular beadwork graphs admit an optimal beadable path corresponding to an Eulerian path in the line graph under the sides constraint.

Topics

graph theory, beadwork design, Eulerian paths, line graphs, symmetry

Domains

graph theory, Eulerian paths, line graphs, regular graphs, craft, jewelry design, ornamental patterning, textile-inspired construction

Methods

graph modeling, line graph transformation, Hierholzer’s algorithm, heuristic path construction

Media

beads, nylon string, acrylic beads, glass beads, bugle beads

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture

Finding Optimal Paths in Beadworks: What If Euler Were a Beader?

Ron Asherov Israel rasherov@gmail.com

Abstract

Forming geometrical or artistic shapes with beads and nylon strings is a popular handcraft, mainly in the oriental world and mostly for purposes of jewelry or decoration. While many geometrical figures can be made using artistic intuition, such figures often have mathematical features worth exploring; both because they are interesting in and of themselves, and also because comprehending these features will allow the practitioner to produce mathematically interesting, symmetrical and aesthetic works. Using ideas from Graph Theory we set out to use computer programs in order to generate instructions for premade beadwork designs

From Beadworks to Graphs

Beadwork is an activity that has taken a place in most cultures throughout human history, mainly for personal adornment, religious purposes, good luck talismans and gifts. In fact, in 2007 researchers found shell beads in North Africa that date as far back as 82,000 years ago [1]. Moreover, creating geometrical beadworks by passing a nylon string through acrylic or glass beads has been a popular hobby in the East, and has, over the past centuries, expanded to locations throughout the world. The mathematical properties of beadwork have recently received attention in the literature [2,3], mostly in reference to the patterns and designs of beadwork and less so to the beading technique, which is what we will attend to here.

In the form of beadwork that we will consider here, that of passing a nylon string through beads, the artist starts with a long piece of thread, then strings beads on it and makes loops to create shapes. Using this approach it is possible to create a variety of geometrical works [4]. However, generally speaking, asymmetry in beadworks is far more likely than symmetry, so stringing the beads in a haphazard manner will in most cases lead to asymmetry in the tension caused by the string, leading to deformations and, consequently, unbalanced and unaesthetic work. We seek a way to avoid such undesired consequences by examining the hidden mathematical features of these types of beadwork. Finding the mathematics behind a well-balanced (and hence aesthetic) beadwork can provide a constructive set of instructions for building more symmetrical and aesthetic beadworks.

Mathematics (specifically, graphs) is the language we use to describe these beadworks. By this analogy, the beads represent the edges of the graph, while the vertices are implied by the crossings of the string. As an illustration, a beadwork and its corresponding graph are given in Figure 1. We believe that while each beadwork can be represented by a mathematical graph, not every graph can represent a beadwork; a graph that represents a beadwork must meet certain conditions that we presently set forth:

1. Connectivity: the graph must be connected, i.e., every pair of vertices is connected by a path¹. This means that the graph represents only one work, and not several disjoint works.
2. Constraints on the degree². This condition is twofold:

¹ In this context, a path from vertex a to vertex b is a sequence of vertices starting with a and ending with b, such that between every two adjacent vertices in the sequence there is an edge. ² The degree of a vertex is the number of edges that touch the vertex.

Asherov

I. Lower bound: every vertex in the graph should touch at least three edges. This is because if it only touches one (a “leaf”), it leads to a dead-end in the beadwork, meaning that the work cannot progress any further. If it touches two edges, the tension caused by the string will deform the vertex and make it look like a long edge, instead of two straight lines. II. Upper bound: depending on the size and the shape of the beads, there is also an upper limit to the degree of each vertex in the graph. The wider the ends of the beads are, the more likely it is that the beads overlap one another, thus deforming the vertex. With round or diamond-shaped beads it is advised to use vertices with degrees 3 or 4. The techniques that will be suggested below even out the tension of the string, so it is also possible to use vertices with degree 5. The upper bound can be pushed further if bugle beads (that are long and narrow) are used.

Figure 1. A two dimensional beadwork and its graph. This is a part of the infinite semi-regular tiling of the Euclidean plane known as the rhombitrihexagonal tiling (vertex configuration 6.4.3.4).

Assuming we have a graph from which we wish a beadwork to be built (i.e., a graph that meets the three conditions above), one can start forming the work intuitively by threading the string wherever one sees fit or according to whatever seems right. But as mentioned, intuitive work will most likely result in an unbalanced work in the sense given above (asymmetry and deformation). Hence intuitive work, because of its random nature, is more likely to be unaesthetic. We want a balanced work because it is more aesthetic, i.e. more symmetrical and less deformed. Intuitively we cannot work it out, so we seek a mathematical algorithm to generate instructions for the beading process. Before we continue to the algorithm, let us consider what a well-balanced work is insofar as it is expressed in a graph. Below are stipulations for a well balanced beadwork as it is expressed in a path in the graph:

1. We look for a single path that meets these conditions, as we will use one piece of string and not several.
2. Connecting every pair of adjacent edges to keep the adjacent edges close to each other, and to make the vertices more obvious.
3. Doing so exactly once to keep the symmetry and minimize the length of the string used.

An example of what a vertex in a perfect beadwork should look like is given in Figure 2. The language developed earlier allows us to translate a problem in the world of beadworks into a general mathematical problem. By doing so we can tackle the problem at hand using more sophisticated tools belonging to the world of mathematics. The problem is thus as follows: Given a graph that meets the three conditions above, we seek a path in it that connects every pair of adjacent edges exactly once (if such a path exists). An example of an “optimal beading” of the tetrahedron is given in Figure 3.

Finding Optimal Paths in Beadworks: What If Euler Were a Beader?

Mathematical Analysis and Results

Since our interest lies in relation between the edges of the graph, it is helpful to consider the line graph [5] $L(G)$ of the graph $G$ : it is the graph whose vertices are the edges (lines) of the original graph, and two vertices in $L(G)$ are connected by an edge, if and only if the edges represented by these vertices share a common endpoint in $G$ . If the set of edges of the graph $G$ is $E$ and the set of vertices is $V$ , then the line graph $L(G)$ has $|V^{\prime }|=|E|$ vertices and $|E^{\prime }|=\frac{1}{2}{\sum }_{v\in V}{\mathrm{deg}}^2(v)-|E|$ edges. As an illustration, the graph representing the tetrahedron and its line graph are given in Figure 4. A path in the physical beadwork is easily translated into a path in the mathematical graph or in its line graph; the optimal path in Figure 3 will be noted as 3-1-2-3-5-6-1-5-4-2-6-4.

Figure 2. Ideal vertex of degree five. Note that the thread passes through every pair of edges, resulting in a balanced work.

Figure 3. Optimal path in a skeleton of a tetrahedron. The two ends of the string are to be tied. Note that every adjacent pair of edges is connected exactly once.

In an optimal path, every edge of the original graph is connected exactly once to any adjacent edge. In terms of the associated line graph, we want the path to pass through every edge exactly once, or in other words, we look for an Eulerian path in the line graph. Unfortunately, the analogy is imperfect; we cannot use any Eulerian path in the line graph because not every such path is realizable in the beadwork. For example, consider the path 3-5-1. Even though it is a legitimate path in the line graph, it is not realizable in the physical beadwork because while passing the thread from edge 3 to edge 5, it is not possible to proceed to edge 1 (but to edges 4 and 6).

There are many ways to find Eulerian paths and circuits in an undirected connected graph, if such a graph exists. However, given a line graph and a path in it, there is no easy way to determine if the path is realizable, even though as it is proved in [6], it is possible to retrieve the original graph from the line graph (except for one particular case). In order to solve this difficulty, we partition every node of the line graph into two “sides,” with respect to the two ends of the corresponding edge in the original graph. This is closer to reality, because beads also have two sides. For example, in the graph given in Figure 4, vertex 1 is partitioned into $1-a$ that is connected to vertices 3 and 5, and $1-b$ that is connected to vertices 2 and 6.

The nature of the beading process implies that a path in the line graph is realizable in beadwork if and only if for every vertex the path “enters” it and “exits” from it through different sides of the vertex. That way, if we get to vertex 1 from vertex 3, that means we got to the vertex from its a-side, so we must exit through the vertex’s b-side, namely vertices 2 or 6. Now the analogy is perfect: an optimal beading path corresponds to an Eulerian path in the line graph under the “sides constraint” (and vice versa).

An ideal beadable path exists in the line graph if every vertex’s a-degree equals to its b-degree. This is equivalent to saying that every vertex of the original graph has the same degree, or in other words, that

Asherov

the original graph is regular. We show this by providing an algorithm to find such a path, adopted from the well-known Hierholzer’s algorithm to find Eulerian paths in usual graphs [7].

Figure 4. The graph representing the skeleton of a tetrahedron and its line graph.

Assuming every vertex’s a-degree equals to its b-degree, we pick a random vertex (in the line graph). We then repeatedly randomly pick an edge, remove it and move to the next vertex. We do that until it is no longer possible; the process forms a path in the graph. Because of the equality of the degrees, every time we visit a vertex there will be a proper way out (if we got to a vertex from its a-side, we must also have an unused edge coming from the vertex’s b-side, so we can pick it). From that it follows that the resulting path is closed, or a circuit. However it may be possible that we have not covered all edges by that; in that case, we then again pick a random vertex in our circuit, that has an unused edge, and follow the procedure. We add the resulting circuit to the original path, and continue in that manner until all edges are covered (at the end we will cover all edges because the graph is connected).

We conclude that in regular graphs (that represent a beadwork) it is possible to find a beadable Eulerian path, and so their corresponding beadworks can be strung in an optimal manner, to make it well-balanced and aesthetic. Several heuristic methods can be employed to generate a path that is easier to bead by hand (e.g. enclose small polygons if possible); these methods usually replace the random selection of the vertices and the edges in the (line) graph. Further work should research the case where the graph is not regular; it is conjectured that a solution for the Chinese Postman Problem [8] can be adopted to solve the problem.

References

[1] A. Bouzouggar et al. 82,000-year-old shell beads from North Africa and implications for the origins of modern human behavior. Proceedings of the National Academy of Sciences 2007. [2] G. Fisher and B. Mellor. Using tiling theory to generate angle weaves with beads. Journal of Mathematics and the Arts 6.4 (2012): 141-158. [3] E. Baker and S. Goldstine. Bead Crochet Bracelets: What Would Escher Do? Proceedings of the Bridges Conference 2012. [4] L. M. Shea. The Seven Principles of Angle Stitching - a Geometrically Based Beading Technique. Proceedings of the Bridges Conference 2012. [5] F. Harary and R. Z. Norman. Some properties of line digraphs. Rend. Circ. Mat. Palermo (2) 9 (1960), 161-168. [6] H. Whitney. Congruent graphs and the connectivity of graphs. American Journal of Mathematics 54 (1932): 150-168. [7] C. Hierholzer. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6 (1): 30-32. [8] M-K Kuan. Graphic programming using odd or even points. Chinese Mathematics 1962; 1:273-277.