Building Polyhedra from Polygons with Colored Edges

Year: 2015 Authors: Ioana Browne; Mircea Draghicescu

Core claim

Graph-theoretic edge-coloring results yield small complete sets of polygon colorings for building many polyhedra, including all polyhedra with triangular and square faces.

Topics

polyhedral construction, edge coloring, complete coloring sets, geometric toys, graph theory

Domains

graph theory, equitable edge coloring, polyhedral graphs, combinatorics, geometric design, construction systems, paper sculpture, educational craft

Methods

graph reformulation, color-signature analysis, theorem proof, constructive examples

Media

polygonal pieces, colored edges, notched rigid material, polyhedron models

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 2015: Mathematics, Music, Art, Architecture, Culture

Building Polyhedra from Polygons with Colored Edges

Ioana Browne and Mircea Draghicescu ITSPHUN LLC anca@itsphun.com, mircea@itsphun.com

Abstract

If we color the edges of a polyhedron and then break it apart into its polygonal faces we obtain a set of polygons with colored edges. We explore here the opposite problem: find sets of polygons with colored edges that can be assembled into various polyhedra by joining them along edges of the same color. We show how solutions to this problem can be used to design construction systems for building strong polyhedra models.

Introduction

There are many geometric construction systems and toys that can be used to assemble polyhedra models by joining together polygonal faces on a common edge. One of the simplest systems consists of (roughly) polygonal shapes that can be connected by sliding them together along slits, cuts, or notches ([5], [7]). Most connection mechanisms allow polygons to be connected along any two edges of equal length, but here we are interested in systems that impose some restrictions on which edges can be joined together. In particular, we will consider an abstract model consisting of regular polygons with equal-length edges, each colored with one of two colors; the connections can be made only along edges that have the same color.

By definition, two such polygons are equivalent if we can map one to the other by a polygon transformation, i.e., a rotation, or, if the construction system being modeled allows “flipping” the polygonal pieces, a reflection. The equivalence class of a polygon will be called its coloring. A set $C$ of colorings is complete for some class of polyhedra if all polyhedra in the class can be built using only polygons that have colorings in $C$ . The set of all colorings of regular polygons with at most $n$ sides is clearly complete for all polyhedra with such faces. The number of colorings grows exponentially with $n$ ; the goal of this paper is to show that there exist smaller complete sets of colorings for various classes of polyhedra. (The set of trivial colorings with one color is also complete for all polyhedra, but we are interested here in colorings that use both colors.)

Referring to Figures 1 and 2, a tetrahedron, octahedron and icosahedron can be built using 4 equivalent triangles of any of the triangle colorings; the minimal complete coloring sets for these 3 polyhedra are thus $\{T_1\},\{T_2\},\{T_3\},\{T_4\}$ . A cube can also be built with all faces having the same coloring as long as that coloring is not $S_6$ ; minimal complete sets are $\{S_1\},\{S_2\},\{S_3\},\{S_4\},\{S_5\}$ . $\{T_3,S_1\},\{T_3,S_2\},\{T_3,S_5\}$ are minimal complete sets for the square pyramid, but $\{T_3,S_3,S_4,S_6\}$ is not complete. $\{T_3,T_4,S_3\},\{T_1,S_6\},\{T_3,S_3,S_5\},\{T_3,S_3,S_6\},\{T_3,S_5,S_6\}$ , etc., are minimal complete sets for the triangular prism, while $\{T_3,T_4,S_6\},\{T_1,T_2,T_3,T_4,S_5\},\{T_3,S_3,S_4\},\{T_3,S_4,S_5\}$ , etc., are not complete. By counting the number of edges of the two colors we can see that $\{T_1,T_3,S_2,S_4,S_5,S_6\}$ and $\{T_1,T_3,T_4,S_2,S_4\}$ are not complete for the cuboctahedron.

Figure 1: The triangle and square colorings (they are the same with or without reflections)

Browne and Draghicescu

Figure 2: Octahedron $(T_3)$ , cube $(S_5)$ , square pyramid $(T_3,T_4,S_6)$ , triangular prism $(T_3,S_3,S_5)$

Figure 3: Pentagonal piece with one reversed notch and a dodecahedron lantern built with such pieces

We will prove that $\{T_3,T_4,S_5,S_6\}$ is complete for all polyhedra with triangular and square faces. We also conjecture that $\{T_3,T_4,S_4,S_5\}$ is complete for convex polyhedra with triangular and square faces.

Motivation

The motivation for this work comes from designing the ITSPHUN system of geometric shapes ([1]). The original design, like the systems mentioned above, has polygonal pieces with notches along their edges, all pointing in the same direction, either clockwise or counter-clockwise. This makes it easy to assemble a polyhedral model since the pieces, even when made from a relatively rigid material, can be gradually rotated into their final position. The uniform notch direction also makes it easy to disassemble a model by reversing the rotation, but has the disadvantage that pieces can sometimes rotate out of position by themselves causing the model to come apart. To counter this, we started experimenting with reversing the directions of some of the notches; a piece can thus have notches pointing in both directions, as illustrated in Figure 3. This makes the assembly process more difficult (but still possible due to the elasticity of the material) but prevents a piece from accidentally rotating out of position. Unless we have pieces with all possible combinations of notch directions, assembling a model now involves solving a puzzle since not every piece will fit at every location. We can represent the two notch directions by two “colors” and the need to minimize the number of different kinds of pieces while still allowing the construction of a large class of polyhedra models led us to the problem explored here.

Graph Results

The original problem can be restated as an edge coloring problem on graphs by representing a polyhedron $P$ by the graph $G(P)$ which has as nodes the faces of $P$ and as edges the edges of $P$ . (If $P$ is convex, $G(P)$ is the polyhedral graph of the dual of $P$ .)

Let $R$ and $B$ be two colors and let $G=(V,E)$ be a graph with set of vertices $V$ and set of edges

Building Polyhedra from Polygons with Colored Edges

$E$. An (edge) coloring of $G$ (not to be confused with the polygon coloring defined previously) is a map $c:E\to \{R,B\}$. For coloring $c$ and $v\in V$, let $d_X^c(v)$ be the number of $X$ edges incident to $v$, $X\in \{R,B\}$ and $s^c(v)=⟨d_R^c(v),d_B^c(v)⟩$ the color signature of $v$ in $c$. Note that color signatures do not distinguish between different ways in which polygon edge colors are cyclically ordered around a polyhedral face; we will discuss this in the next section.

Restating the problem described in the introduction in terms of graphs, a set of color signatures is complete for a class of graphs if any graph in the class has a coloring $c$ such that $s^c(v)\in S$ for all vertices $v$. We are looking for small sets of color signatures that are complete for certain graph classes.

Hilton and de Werra ([2], [6]) proved that all graphs have a nearly equitable coloring, i.e., a coloring $c$ that satisfies $|d_R^c(v)-d_B^c(v)|\le 2$. The following theorem strengthens this result; a simple proof appears in the full version of this paper at http://www.itsphun.com/coloring.pdf.

Theorem 1. Any graph $G=(V,E)$ has a coloring $c$ satisfying, $\forall v\in V$,

Having obtained a complete set of color signatures where the two colors are roughly balanced ($\{⟨r,b⟩\mid |r-b|\le 2,rb$ even), we will present now a complete set for convex polyhedra where the number of edges of one color (say $R$) incident to a vertex is as small as possible without becoming 0: \{\langle r, b \rangle \mid 1 \leq r \leq 2, b > 0\}.

Theorem 2. For any convex polyhedron $P$, the graph $G(P)$ has a coloring $c$ satisfying $1\le d_R^c(v)\le 2$ and d_B^c(v) > 0 for all nodes $v$.

The proof, which appears in the full version of the paper, is based on Gao and Richter’s theorem ([3], [4]) which states that any polyhedral graph has a closed walk visiting every vertex once or twice (a 2-walk).

Back to Polyhedra

Representing polygons as graph nodes abstracts away the sequence of edges around the polygon; for example, the two square colorings with two $R$ edges and two $B$ edges ($S_5,S_6$ in Figure 1) are represented by the single (graph node) color signature $⟨2,2⟩$. Translating the graph results from the previous section back to polyhedra requires that we consider all possible arrangements of colored edges when defining a complete set of polygon colorings.

With this in mind, according to Theorem 1, we can build any polyhedron with 2 triangle colorings $(T_3,T_4)$, 2 squares $(S_5,S_6)$, 4 pentagons $(P_5,P_6,P_7,P_8$ in Figure 4), 6 hexagons, etc. (The number of colorings for other polygons depends on whether reflections, or flipping of polygons, are allowed or not). For building convex polyhedra, a different complete set of colorings is obtained from Theorem 2: 2 triangles $(T_3,T_4)$, 3 squares $(S_4,S_5,S_6)$, 3 pentagons $(P_4,P_6,P_8)$, 4 hexagons, etc., and, in general, $1+\lfloor \frac{n}{2}\rfloor$ colorings of an $n$-sided polygon. (This number is the same whether we allow reflections or not.)

If the two colors represent notch directions, as described in the “Motivation” section, then flipping a polygon amounts to swapping the two colors. If this is possible, we can reduce the number of colorings given by Theorem 1 to 1 triangle, 2 squares, 2 pentagons, 3 hexagons, etc. For the complete set given by Theorem 2, the only reduction is from 2 to 1 in the number of triangle colorings.

The following conjecture states that the complete set of color signatures given by Theorem 2 can be translated to an equal number of polygon colorings, avoiding the need to include all possible arrangements of colored edges.

Browne and Draghicescu

Figure 4: The pentagon colorings (they are the same with or without reflections)

Conjecture 3. Any convex polyhedron with regular faces can be built with the set that has, for each polygon, a coloring with one $R$ edge and a coloring with two adjacent $R$ edges.

If true, Conjecture 3 reduces the number of colorings in a complete set to just 2 for each polygon: $T_3,T_4$ for triangles, $S_4,S_5$ for squares, $P_4,P_6$ for pentagons, etc.

Conclusions and Future Work

We used graph-theoretical results to solve a practical problem in the design of systems for building polyhedral models from polygonal pieces. If each polygon edge is colored with one of two colors and the connections can be made only along edges of the same color, we showed that it is possible to avoid the combinatorial explosion of required polygon colorings. For pieces that connect through notches along their edges, colors can represent notch directions and our results can be used to design systems for building structurally strong polyhedra models using relatively few piece types.

Possible generalizations include construction systems where edges can be colored with more than two colors and systems with non-symmetrical (e.g., gendered) connections.

References

[1] I. Browne, M. Browne, M. Draghicescu, C. Draghicescu, and C. Ionescu. A fun approach to teaching geometry and inspiring creativity. In G. W. Hart and R. Sarhangi, editors, Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture, pages 587-592, Phoenix, Arizona, USA, 2013. Tessellations Publishing. [2] D. de Werra. Equitable colorations of graphs. ESAIM: Mathematical Modelling and Numerical Analysis - Modlisation Mathmatique et Analyse Numrique, 5(R3):3-8, 1971. [3] Z. Gao and R. Richter. 2-walks in circuit graphs. Journal of Combinatorial Theory, Series B, 62(2):259-267, 1994. [4] Z. Gao, R. B. Richter, and X. Yu. 2-walks in 3-connected planar graphs. Australasian. J. Combinatorics, pages 117-122, 1995. [5] G. W. Hart. “Slide-Together” Geometric Paper Constructions. In Bridges for Teachers, Teachers for Bridges, Workshop Book, pages 31–42, 2004. [6] A. Hilton and D. de Werra. A sufficient condition for equitable edge-colourings of simple graphs. Discrete Mathematics, 128(13):179-201, 1994. [7] J. Miller and E. Akleman. Edge-Based Intersected Polyhedral Paper Sculptures Constructed by Interlocking Slitted Planar Pieces. In Proceedings of Bridges Conference on Mathematical Connections in Art, Music, and Science, Leeuwarden, The Netherlands, July 2008.