Constructing Triangulations and Polyhedra with Dihedral Symmetry

Year: 2025 Authors: Meike Weiß; Vanishree Krishna Kirekod; Reymond Akpanya; Alice C. Niemeyer; Daniel Robertz

Core claim

Grünbaum-colorings enable the construction of maximal planar graphs that embed as congruent-triangle polyhedra with dihedral symmetry.

Topics

planar triangulations, dihedral symmetry, congruent triangles, graph embeddings

Domains

graph theory, planar graph theory, polyhedral combinatorics, group actions, polyhedra, visual geometry, computational design

Methods

Grünbaum-coloring, distance equations, computer algebra, embedding construction

Media

Euclidean 3-space, GAP, Maple, GAPic

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.

Bridges 2025 Conference Proceedings

Constructing Triangulations and Polyhedra with Dihedral Symmetry

Meike Weiß${}^1$, Vanishree Krishna Kirekod${}^2$, Reymond Akpanya${}^3$, Alice C. Niemeyer${}^4$ and Daniel Robertz${}^5$

Chair of Algebra and Representation Theory, RWTH Aachen University, Germany ${}^1$weiss@art.rwth-aachen.de, ${}^3$akpanya@art.rwth-aachen.de, ${}^4$alice.niemeyer@art.rwth-aachen.de

Chair of Algebra and Number Theory, RWTH Aachen University, Germany ${}^2$krishna.kirekod.vanishree@rwth-aachen.de, ${}^5$daniel.robertz@rwth-aachen.de

Abstract

A planar triangulation is a planar drawing of a maximal planar graph such that any two edges intersect at most at their endpoints and each face is bounded by a cycle of length three contained in the planar graph. In this paper, we investigate the construction of polyhedra arising from maximal planar graphs. In particular, we construct a family of maximal planar graphs with dihedral automorphism groups. Moreover, we demonstrate that these graphs can be realized as polyhedra with congruent triangular faces in the Euclidean 3-space having dihedral symmetry groups. We achieve this result by exploiting Grünbaum-colorings.

Introduction

Over the years, graphs have fascinated both mathematicians and artists. Their combinatorial structures spark curiosity and offer endless possibilities to explore patterns, relationships, and ideas that often inspire creative and visually striking designs, see [5, 6, 12, 20, 22]. A question that often arises in the study of graphs is:

Question. How can we produce a “nice” drawing of a given graph?

We refer to a graph drawing as “nice” if it clearly reveals several properties of the corresponding graph through its visual representation. For instance, in this paper, we investigate planar graphs which can be drawn in the Euclidean plane such that any two drawn edges of the given graph are only allowed to intersect at their endpoints. Another desirable property is to have a straight-line planar drawing which Tutte constructs in the case of a given 3-connected planar graph, as discussed in [24]. The study of 3-connected planar graphs turns out to be intriguing, as these are exactly the graphs that are formed by the vertices and edges of a polyhedron, according to Steinitz’s theorem [23]. This study becomes particularly interesting when considering maximal planar graphs, i.e. 3-connected planar graphs, where all faces of a planar drawing (called planar triangulation) are bounded by cycles of length three known as 3-cycles. Hence, this class of planar graphs naturally opens up the following question:

Question. Can a planar triangulation be realized in Euclidean 3-space as a polyhedron consisting of congruent triangles as faces?

This question has been addressed in various works. For instance, Miller (in [14]) resp. Brakhage et al. (in [3]) investigate the planar triangulation that describes the incidence structure of an icosahedron and classify icosahedra with scalene resp. equilateral triangles as faces. Moreover, in [1] and [4] the authors construct polyhedra with prescribed non-trivial symmetry groups. We further refer the reader to [7, 8, 15, 19] for studies on the construction of polyhedra with congruent polygons as faces.

In this paper, we are interested in the construction of highly symmetric polyhedra. In particular, we construct an infinite family of maximal planar graphs and compute corresponding polyhedra whose surfaces

349

Wei et al.

consist of congruent triangles and have dihedral symmetry groups. Note that we exploit the computer algebra systems GAP [9] and Maple [13] to utilize the functionalities provided by the packages [18] and [21], respectively. The illustrations in this paper are generated using the GAP package GAPic [17]. In [2] we provide our implementations to construct the maximal planar graphs and the corresponding polyhedra discussed in this paper.

Preliminaries

In this work, we follow the terminology from [16], including concepts such as planar graphs, connectivity and (induced) subgraphs, to name a few. We focus on planar graphs where adding an edge between any two non-adjacent vertices yields a non-planar graph. In the literature, these graphs are called maximal planar graphs. It can be observed that such a graph is 3-connected, i.e. the graph remains connected even after removing at most 2 vertices, and can be drawn in the Euclidean plane to obtain a planar triangulation. This planar triangulation subdivides the plane into connected components called faces that are all bounded by 3-cycles. By Whitney (see [26]), it follows that every maximal planar graph has a unique planar triangulation and hence a unique set of triangular faces. Consequently, we define a triangulation $T:=(V,E,F)$ as a triple, where $G_T:=(V,E)$ is a maximal planar graph and $F$ is the set of faces in the corresponding planar drawing of $G_T$ . The automorphism group $\mathrm{Aut}(T)$ of a triangulation $T=(V,E,F)$ is the subgroup of the automorphism group of $G_T$ which leaves the set $F$ invariant. Since $G_T$ is 3-connected and planar, we know that $\mathrm{Aut}(G_T)=\mathrm{Aut}(T)$ , see [25]. In addition, a triangulation $T$ can be equipped with a Grünbaum-coloring (see [11]). Here, a Grünbaum-coloring of $T=(V,E,F)$ is a map $\omega :E\to \{\mathrm{r},\mathrm{g},\mathrm{b}\}$ such that for each 3-cycle forming a face, the corresponding edges are colored differently. Note that a planar triangulation can have more than one Grünbaum coloring.

As an example, we consider the graph $G_T=(V,E)$ that forms a triangulation of the octahedron. In this case, $G_T$ can be drawn as a planar triangulation and can be Grünbaum-colored as illustrated in Figure 1a. By examining the illustration below, we see that the arising faces of $G_T$ are given by $F=\{(v_1,v_2,v_3),(v_1,v_2,v_5),(v_1,v_3,v_4),(v_1,v_4,v_5),(v_2,v_3,v_6),(v_2,v_5,v_6),(v_3,v_4,v_6),(v_4,v_5,v_6)\}$ and $T=(V,E,F)$ forms the corresponding triangulation.

(a)

(b) Figure 1: (a) Triangulation $T$ of the octahedron with a Grünbaum-coloring and (b) polyhedron that corresponds to $T$ .

We aim to realize certain triangulations as polyhedra with congruent triangles as faces by using corresponding Grünbaum-colorings. To achieve this, we associate each edge color with a chosen edge length and analyze the resulting distance equations. For simplicity, we define $\Lambda$ as the set that consists of triples (a,b,c) \in \mathbb{R}_{>0}^{3} satisfying the triangle inequalities: $a+b\ge c$ , $a+c\ge b$ and $b+c\ge a$ . Hence, let $\omega$ be a Grünbaum-coloring and $({\ell }_r,{\ell }_g,{\ell }_b)\in \Lambda$ , where ${\ell }_r$ ( ${\ell }_g$ and ${\ell }_b$ ) corresponds to the length of an edge that is colored $r$ ( $g$ and $b$ , respectively). Then, an $({\ell }_r,{\ell }_g,{\ell }_b)$ -embedding of $T=(V,E,F)$ is a map $\varphi :V\to {\mathbb{R}}^3$

Constructing Triangulations and Polyhedra with Dihedral Symmetry

such that all vertices ${\nu }_i,{\nu }_j\in V$ with $\{{\nu }_i,{\nu }_j\}\in E$ satisfy the distance equation

where $\omega (\{{\nu }_i,{\nu }_j\})=k$ with $k\in \{r,g,b\}$ . By combining the incidence structure of $T$ and the $({\ell }_r,{\ell }_g,{\ell }_b)$ -embedding $\varphi$ , we obtain a polyhedron in ${\mathbb{R}}^3$ . Here, we call this polyhedron an embedded triangulation and denote it by ${\mathcal{T}}^{\varphi }$ . The symmetry group of ${\mathcal{T}}^{\varphi }$ consists of all isometries of ${\mathbb{R}}^3$ that leave ${\mathcal{T}}^{\varphi }$ invariant, i.e. $\psi (\varphi (V))=\varphi (V)$ for every isometry $\psi$ in the symmetry group of ${\mathcal{T}}^{\varphi }$ . For instance, if $T$ is the triangulation illustrated in Figure 1a, then a $(\sqrt{2},\sqrt{2},\sqrt{2})$ -embedding $\varphi$ of $T$ is given by $[\varphi ({\nu }_1),\dots ,\varphi ({\nu }_6)]=[(1,0,1),(1,1,0),(2,1,1),(1,1,2),(0,1,1),(1,2,1)]$ . This embedding gives rise to the polyhedron shown in Figure 1b which forms an octahedron in ${\mathbb{R}}^3$ .

Construction of Triangulations with Dihedral Symmetry

In this section, we define an infinite family $(T_{2n}{)}_{n\in {\mathbb{N}}_{\ge 2}}$ of triangulations such that the automorphism group of $T_{2n}$ is isomorphic to the dihedral group $D_{2n}$ (of order $4n$ ), for $n\ne 3$ . To describe the construction of $T_{2n}$ we exploit wheel and ring graphs illustrated in Figures 2a to 2c. Let $T_{2n}$ be the triangulation containing the vertices $\nu ,w,{\nu }_1,\dots ,{\nu }_{2n},w_1,\dots ,w_{2n}$ such that $G:=G_{T_{2n}}$ can be decomposed into the following three induced subgraphs:

1. $G[\{\nu ,{\nu }_1,\dots ,{\nu }_{2n}\}]$ forming a wheel graph, see Figure 2a,
2. $G[\{{\nu }_1,\dots ,{\nu }_{2n},w_1,\dots ,w_{2n}\}]$ forming a ring graph, see Figure 2c and
3. $G[\{w,w_1,\dots ,w_{2n}\}]$ forming a wheel graph, see Figure 2b.

(a)

(b)

(c)

Figure 2: (a) and (b) wheel graphs with $2n+1$ vertices each and (c) ring graph with $4n$ vertices.

The triangulation $T_{2n}$ is shown in Figure 3 and we observe that for every $n\ge 2$ the triangulation $T_{2n}$ can be equipped with a Grünbaum-coloring. Note that in Figure 2c and in Figure 3 the vertices ${\nu }_1$ and $w_1$ appear twice. These vertices are drawn twice solely to provide a simplified illustration of the graphs. Hence, these pairs are identified in the combinatorial structure of the corresponding graphs.

Wei et al.

Figure 3: Triangulation $T_{2n}$ with $4n+2$ vertices and a Grünbaum coloring.

For $n\ge 2$ and $n\ne 3$ , the automorphism group of the triangulation $T_{2n}$ is given by $\mathrm{Aut}(T_{2n})=⟨\sigma ,\tau ⟩$ with the permutations $\sigma$ and $\tau$ defined by

$\sigma :=(v,w)(v_1,w_2,v_3,\dots ,v_{2n-1},w_{2n})(w_1,v_2,w_3\dots ,w_{2n-1},v_{2n})$ and

$\tau :={\prod }_{i=1}^{n-1}(v_{1+i},v_{2n+1-i})(w_{1+i},w_{2n+1-i}).$

Since the generators of $\mathrm{Aut}(T_{2n})$ satisfy ${\tau }^2={\sigma }^{2n}=1$ and $\tau \sigma \tau ={\sigma }^{-1}$ and $\mathrm{Aut}(T_{2n})$ contains exactly $4n$ elements, the group $\mathrm{Aut}(T_{2n})$ is indeed a dihedral group of order $4n$ . Note that $\tau$ is a reflection that fixes ${\nu }_1,{\nu }_{n+1},w_1$ and $w_{n+1}$ . Further, with the help of GAP, we have been able to verify that the triangulation $T_{2\cdot 3}$ has an automorphism group that is isomorphic to $C_2\times S_4$ , which contains a dihedral group of order 12 as a proper subgroup. Moreover, we observe that $T_{2\cdot 3}$ describes the incidences between the vertices and edges of the polyhedron that results from a cube by replacing each of its faces with a square pyramid, see [6].

Construction of Polyhedra with Dihedral Symmetry

Now, we construct $({\ell }_r,{\ell }_g,{\ell }_b)$ -embeddings of the triangulation $T_{2n}=(V,E,F)$ , where $n\ge 2$ and $n\ne 3$ , such that the resulting polyhedra have dihedral symmetry groups of order $4n$ . Since the vertices of $T_{2n}$ are given by $\nu ,w,{\nu }_1,\dots ,{\nu }_{2n},w_1,\dots ,w_{2n}$ , we can make use of the incidence structure as illustrated in Figure 3.

First, we assign 3D-coordinates to the vertices ${\nu }_1,\dots ,{\nu }_{2n},w_1,\dots ,w_{2n}$ of the ring graph using the following idea: Let r_1,h_1\in \mathbb{R}_{>0} be positive real numbers, $\alpha :=\frac{\pi k}{n}$ for $k\in \mathbb{N}$ with $\gcd (2n,k)=1$ and $r_2:=|r_1\cos (\alpha )|$ . We aim to place the vertices ${\nu }_1,\dots ,{\nu }_{2n}$ on the $xy$ -plane with $z=h_1$ such that

• the coordinates corresponding to $({\nu }_2,{\nu }_4,\dots ,{\nu }_{2n})$ form an $n$ -gon with corners lying on the circle of radius $r_2$ centered at $(0,0,h_1)$ and
• the coordinates corresponding to $({\nu }_1,{\nu }_3,\dots ,{\nu }_{2n-1})$ form an $n$ -gon with corners lying on the circle of radius $r_1$ centered at $(0,0,h_1)$ .

Similarly, the vertices $w_1,\dots ,w_{2n}$ are embedded in the same manner along two concentric circles in the $xy$ -plane, centered at $(0,0,-h_1)$ , by swapping $r_1$ and $r_2$ . Hence, the coordinates of $v_1,\dots ,v_{2n}$ and the coordinates of $w_1,\dots ,w_{2n}$ are contained in two parallel planes. We refer to Figure 4 for a visual representation of this construction. The desired embedding of $T_{2n}$ is then completed by assigning 3D-coordinates to the vertices

Constructing Triangulations and Polyhedra with Dihedral Symmetry

$v,w$ such that the faces corresponding to the wheel graphs are congruent to the faces corresponding to the ring graph.

(a) Figure 4: Embedding of the vertices of the ring graph with $n=4$ and $k=1$ : (a) top view and (b) part of the side view.

(b)

More precisely, for $({\ell }_r,{\ell }_g,{\ell }_b)\in \Lambda$ , we construct an $({\ell }_r,{\ell }_g,{\ell }_b)$ -embedding $\varphi :V\to {\mathbb{R}}^3$ as follows: The images of the vertices $v_1,\dots ,v_{2n}$ under $\varphi$ can be defined as

and the images of $w_1,\dots ,w_{2n}$ under $\varphi$ as

With $h_2:=\sqrt{4h_1^2+r_1^2-2r_1{r}_2}$ , we define $\varphi (v)$ and $\varphi (w)$ as

By construction, the resulting polyhedron ${\mathcal{T}}^{\varphi }$ consists of congruent triangular faces and has a symmetry group that is isomorphic to the dihedral group of order $4n$ . We observe that the edge lengths of ${\mathcal{T}}^{\varphi }$ are given by

Our construction leads to certain embeddings of $T_{2n}$ where the edge lengths are defined by the parameters $k,r_1$ and $h_1$ . For given values of $r_1$ and $h_1$ , our proposed construction yields $\phi (n)$ distinct $({\ell }_r,{\ell }_g,{\ell }_b)$ -embeddings of the Grünbaum-colored triangulation $T_{2n}$ , where $\phi$ denotes the Euler’s totient function. Moreover, the

Wei et al.

polyhedron obtained from our construction for given $r_1,h_1$ has self-intersections if $k\notin \{1,2n-1\}$ . Note that the question whether there exists an $({\ell }_r,{\ell }_g,{\ell }_b)$ -embedding of $T_{2n}$ for every $({\ell }_r,{\ell }_g,{\ell }_b)\in \Lambda$ remains open.

In Figures 5 and 6, we illustrate different polyhedra that can be constructed by embedding the triangulation $T_{2.4}$ into ${\mathbb{R}}^3$ via suitable $({\ell }_r,{\ell }_g,{\ell }_b)$ -embeddings that are obtained from the above method. In the figures, the vertices $\nu$ and $w$ are colored in dark green, and the vertices ${\nu }_1,\dots ,{\nu }_8$ and $w_1,\dots ,w_8$ are colored in orange for better illustration.

(a)

(b)

(a) Figure 6: Different views of the embedding of $T_{2.4}$ for $k=3$ .

Figure 5: Different views of the embedding of $T_{2.4}$ for $k=1$ . (b)

Constructing Triangulations and Polyhedra with Dihedral Symmetry

Furthermore, in Figure 7 we present photographs of 3D-printed versions of the above polyhedra. In order to create these models we exploited the GAP package [10].

(a) Figure 7: 3D-printed embeddings of $T_{2-4}$ for $k=1$ and $k=3$ .

(b)

Acknowledgements

M. Weiβ, R. Akpanya, A. Niemeyer and D. Robertz acknowledge the funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) in the framework of the Collaborative Research Centre CRC/TRR 280 “Design Strategies for Material-Minimized Carbon Reinforced Concrete Structures - Principles of a New Approach to Construction” (project ID 417002380).

References

[1] R. Akpanya and T. Goertzen. “Surfaces with given Automorphism Group.” arXiv e-prints, Jul. 2023, p. arXiv:2307.12681. [2] R. Akpanya, V. Krishna Kirekod, and M. Weiβ. https://github.com/MeikeWeiss/DihedralEmbedding. [3] K.-H. Brakhage, A. C. Niemeyer, W. Plesken, D. Robertz, and A. Strzelczyk. “The icosahedra of edge length 1.” J. Algebra, vol. 545, 2020, pp. 4-26. https://doi.org/10.1016/j.jalgebra.2019.04.028. [4] K.-H. Brakhage, A. C. Niemeyer, W. Plesken, and A. Strzelczyk. “Simplicial surfaces controlled by one triangle.” J. Geom. Graph., vol. 21, no. 2, 2017, pp. 141-152. [5] G. Brinkmann, F. Buccoliero, and H. Van den Camp. “Preserving and Increasing Symmetries of Polyhedral Maps.” Match Communications in Mathematical and in Computer Chemistry, vol. 93, no. 1, 2024, p. 131–161. http://dx.doi.org/10.46793/match.93-1.131B. [6] J. H. Conway, H. Burgiel, and C. Goodman-Strauss. The symmetries of things. A K Peters, Ltd., Wellesley, MA, 2008. [7] K. Coolsaet and S. Schein. “Some New Symmetric Equilateral Embeddings of Platonic and Archimedean Polyhedra.” Symmetry, vol. 10, no. 9, 2018. https://www.mdpi.com/2073-8994/10/9/382. [8] D. Eppstein. “On polyhedral realization with isosceles triangles.” Graphs Combin., vol. 37, no. 4, 2021, pp. 1247-1269. https://doi.org/10.1007/s00373-021-02314-9.

Weiß et al.

[9] GAP – Groups, Algorithms, and Programming, Version 4.14.0. The GAP Group. 2024. https://www.gap-system.org.

[10] T. Goertzen and C. Amend. “SelfIntersectingComplexes, Version 1.0.” https://github.com/TomGoertzen/SelfIntersectingComplexes. 2024.

[11] B. Grünbaum. “Conjecture 6 in Recent Progress in Combinatorics.” Proceedings of the Third Waterloo Conference on Combinatorics, May 1968. W. T. Tutte, Ed. Academic Press, New York-London, 1969. p. 343.

[12] G. Hart. “Constructing Wooden Polyhedra.” Proceedings of Bridges 2022: Mathematics, Art, Music, Architecture, Culture. D. Reimann, D. Norton, and E. Torrence, Eds. Phoenix, Arizona: Tessellations Publishing, 2022. pp. 41–48. http://archive.bridgesmathart.org/2022/bridges2022-41.html.

[13] Maplesoft, a division of Waterloo Maple Inc.. Maple. Waterloo, Ontario.

[14] E. N. Miller. “Icosahedra constructed from congruent triangles.” Discrete & Computational Geometry, vol. 24, 2000, pp. 437–452.

[15] MIT CompGeom Group, H. A. Akitaya, E. D. Demaine, A. Hesterberg, A. Lubiw, J. Lynch, J. O’Rourke, F. Stock, and J. Tkadlec. “Deltahedral Domes over Equiangular Polygons.” 2024. https://arxiv.org/abs/2408.04687.

[16] B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.

[17] A. Niemeyer, R. Akpanya, T. Görtzen, M. Weiß, and L. Schnelle. “GAPic, Version 0.1.” https://github.com/GAP-ART-RWTH/GAPic. Apr 2025. GAP package.

[18] A. Niemeyer, M. Baumeister, R. Akpanya, T. Görtzen, M. Weiß, and L. Schnelle. “SimplicialSurfaces, Version 0.7.” https://github.com/gap-packages/SimplicialSurfaces. Apr 2025. GAP package.

[19] A. C. Niemeyer, W. Plesken, and D. Robertz. “Simplicial Surfaces of Congruent Triangles.” In preparation, 2025.

[20] L.-C. Peng. “Creating Deltahedra with Unfolded Net of Tetrahedron.” Proceedings of Bridges 2019: Mathematics, Art, Music, Architecture, Education, Culture. S. Goldstine, D. McKenna, and K. Fenyvesi, Eds. Phoenix, Arizona: Tessellations Publishing, 2019. pp. 395–398. http://archive.bridgesmathart.org/2019/bridges2019-395.html.

[21] D. Robertz. “SimplicialSurfaceEmbeddings: a Maple package for the analysis and construction of embedded simplicial surfaces.”

[22] R. Roelofs. “Polyhedra with $90^{\circ }$ Dihedral Angles.” Proceedings of Bridges 2022: Mathematics, Art, Music, Architecture, Culture. D. Reimann, D. Norton, and E. Torrence, Eds. Phoenix, Arizona: Tessellations Publishing, 2022. pp. 33–40. http://archive.bridgesmathart.org/2022/bridges2022-33.html.

[23] E. Steinitz and H. Rademacher. Vorlesungen über die Theorie der Polyeder unter Einschluss der Elemente der Topologie. ser. Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, Berlin-New York, 1976. vol. No. 41. Reprint der 1934 Auflage.

[24] W. T. Tutte. “How to draw a graph.” Proc. London Math. Soc. (3), vol. 13, 1963, pp. 743–767. https://doi.org/10.1112/plms/s3-13.1.743.

[25] H. Whitney. “Congruent Graphs and the Connectivity of Graphs.” Amer. J. Math., vol. 54, no. 1, 1932, pp. 150–168. https://doi.org/10.2307/2371086.

[26] H. Whitney. “2-Isomorphic Graphs.” American Journal of Mathematics, vol. 55, no. 1, 1933, pp. 245–254. http://www.jstor.org/stable/2371127.