Easy-to-Understand Visualization Models of Complete Maps

Year: 2023 Authors: Carlo H. Séquin

Core claim

A flattened pillowcase representation can make complex complete maps on higher-genus surfaces understandable from one or two images.

Topics

complete maps, handle-body visualization, pillowcase model, surface symmetry

Domains

graph theory, topological graph embeddings, genus, map coloring, mathematical visualization, paper model design, 3D printing, origami

Methods

dual graph embedding, front-back diagramming, symmetry search, ad hoc construction

Media

crochet tiles, felt polygons, origami tiles, printed paper 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.

Bridges 2023 Conference Proceedings

Easy-to-Understand Visualization Models of Complete Maps

Carlo H. Séquin

CS Division, University of California, Berkeley, CA, USA; sequin@berkeley.edu

Abstract

A complete map $M_n$ consists of $n$ disk-like regions, where every “country” shares a non-zero-length border-line with all the other $n-1$ countries. Different methods are described for constructing easy-to-understand visualization models of complete maps. One useful representation takes the form of a 2-layered “pillow-case” forming a disk with a minimum number of tunnels. Results are presented for complete maps with eight to twelve countries on symmetrical handle-bodies of genus-2 through genus-6.

Introduction

Complete Maps are duals of Complete Graphs, in which every node is connected to all the other nodes. Complete Map $M_n$ consists of $n$ simply connected regions, where every “country” shares a non-zero-length border-line with all the other $n-1$ countries. Every country has the topology of a disk. Maps with up to four countries can be drawn on a sphere or some other genus-0 surface. Map $M_4$ has the connectivity of a tetrahedron. Maps with 5 to 7 countries can be embedded on a toroidal body of genus 1. Maps $M_5$ and $M_6$ can be drawn with different connectivity, which may be conveyed in several different ways. The most abstract way is a rotation system in the form of a small table (Figure 1(a)) that lists for each country in cyclical order the other $n-1$ countries that it touches. Figure 1(a) describes the layout of the complete graph $K_6$ shown in Figure 1(b). The underlined numbers in Figure 1(a) are the edges that form the unique hexagonal region in this graph layout [7]; all other regions are triangular. The complete hexagonal map (Figure 1(b)) can be turned into a torus by identifying opposite edges. While this diagram is highly symmetrical, it loses this symmetry when it is curled up into a torus, and it is not immediately clear what the individual countries on the toroidal surface will look like.

The complete graph $K_6$ , and thus $M_6$ , can also be drawn on a torus with 3-fold dihedral rotational symmetry (Figure 1(c)). Here the torus is formed by gluing together opposite edges in the marked rectangular area. A single picture or diagram is typically sufficient to describe the layouts of these maps on a genus-1 surface.

(1): 43526 (2): 54631 (3): 65142 (4): 16253 (5): 21364 (6): 32415

(a)

(b)

(c) Figure 1: $M_6$ on torus: (a) rotation system; (b) $K_6$ with a hexagonal region; (c) $D_3$ symmetrical layout.

More physical models may be constructed from tubular crochet segments that are stitched together into intricate handle-bodies [2], or they may result from joining $n$ regular felt polygons with $n-1$ sides, which are sewn together along their edges. Suitable handle-bodies have even been constructed from dozens of specially designed origami tiles by Eve Torrence [10, 11]. All of these physical models are intriguing objects to be explored by touch; however, they do not readily reveal the topology of the underlying map.

Sequin

My goal is to present views of complete maps on symmetrical handle-bodies that can be recognized readily from one or two (front & back) pictures. The challenge starts with 8 countries on a genus-2 handle-body. Heawood’s formula [6] specifies the minimal genus required for a map with $n$ countries:

Handle-bodies of genus $g$ are often represented in the shape of a $g$ -hole torus, i.e., a fat disk with $g$ tunnels passing through it from front to back. On such a handle-body, the layout of the map can be shown with colored diagrams of the front and back sides of the disk. These two layers are stitched together along the outer contour of the disk and along all the $g$ rims of the tunnels, thus forming a kind of flattened “pillow-case,” which would expand into a nicely rounded $g$ -hole torus when inflated. The front- and back-surfaces may also be printed out, glued together, and the holes may be cut out to make it easy to see how countries are connected when they extend through holes or around the outer rim of the disk.

Unfortunately, I don’t know any general algorithm that can construct such models. My search for good models has been ad hoc and rather tedious. In this paper, I focus on complete maps with 8 to 12 countries, and I present the solutions with the highest symmetries that I have found. Sometimes, the chosen handle-body can be a $g$ -hole torus, possibly with $g$ -fold rotational symmetry, or with $(g-1)$ -fold symmetry, where one hole is placed in the center. However, the symmetry of the complete map will typically be lower because the layout of the various countries cannot adhere to the symmetry of the handle-body. To find good solutions, I have followed a few different approaches. They will be described, in turn, in the context of the maps where they have led to useful results.

Pillowcase Extraction, $n=8$

Constructing a pillowcase model for a complete map with eight countries on a genus-2 handle-body was not too difficult since Susan Goldstine has created several physical models of such an 8-color map based on information found in [2]. One of her models is a ceramic tea pot and cup, suitably painted with eight colors [3]. In another model, eight heptagonal crochet tiles have been joined edge-to-edge to form a 2-hole torus (Figure 2(a)). Based on her Bridges paper [4], I have extracted a corresponding embedding of the complete graph $K_8$ on a 2-hole torus (Figure 2(b)). The solid lines are on the front, and the dashed lines are on the backside. This network of curves partitions the surface of the 2-hole torus into 16 triangular faces plus two quadrilaterals. A suitably refined dual representation then leads to the map shown in Figure 2(c,d) (front & back). The border lines between the eight countries form a network with 16 junction points of valence 3 and with two valence-4 junctions (at centers of the top and bottom). When half of Figure 2(c,d) is folded back to form a 2-hole torus, the overall world exhibits simple $C_2$ symmetry, with the $C_2$ rotation axis running vertically through the middle of the folded figure.

Figure 2: (a) Goldstine’s crochet model [4]; (b) a corresponding connectivity graph of $K_8$ ; (c,d) resulting pillow-case model of $M_8$ showing front & back of an unfolded 2-hole torus.

Easy-to-Understand Visualization Models of Complete Maps

The model depicted in Figure 2(c,d) is already easy to visualize. I have tried to find a simpler layout, possibly with a higher degree of symmetry by moving all the nodes to different locations on the 2-hole torus. I moved the red and yellow (black and blue) nodes from the top (and bottom) of the 2-hole stencil to the inner rims of the two holes. Similarly, the white and orange (green and gray) nodes have been moved towards the middle of the side rims of the 2-hole disk. This results in the “less crowded” graph embedding (Figure 3(a)). The solid black lines are on the front, and the dashed red lines are on the backside. Making the latter pattern on the back the same as the one on the front, guarantees overall $C_2$ symmetry. To convert this into the dual map $M_8$ , I consider the nodes of the $K_8$ graph to be the “capitals” of each country, and the arcs in the graph to be direct “highways” between neighboring capitals. About half-way along each highway, I expect to find the border between the two countries. Up to those border points I color the highways with the same color as the capital. This yields a good indication of the extent of each country and its overall shape. By connecting such border points and simplifying and smoothing the resulting shape, I then obtain the 8-country map shown in Figure 3(c,d). This world still has overall $C_2$ symmetry.

(a)

(b)

(c,d) Figure 3: (a) A more “streamlined” embedding of $K_8$ . (b) Colored “roads” to neighboring “capitals.” (c,d) Corresponding map $M_8$ on a 2-hole disk, front & back, unfolded.

The Dual of a Symmetrical Graph Embedding, $n=9$

A complete map of nine countries must be accommodated on a handle-body with a genus of at least 3. For this case, I had no nicely colored model that I could use as a starting point. So, I started by trying to draw the complete graph $K_9$ on a 3-hole torus with 3-fold rotational symmetry. The nine nodes of the complete graph $K_9$ can be placed on the rims of the three holes, while maintaining the 3-fold rotational symmetry. I also managed to place all the 36 edges of the graph, while maintaining at least $C_3$ symmetry. This resulted in a map with 22 triangular facets and one hexagonal region (Figure 4(a)). I have marked the triangular regions between the graph edges with small triangles. The dark ones are on the front surface of the torus; the white ones are on the back, and the ones with a dark outline stretch from front to back.

Figure 4(b) shows a physical model made out of nine felt octagons by Ellie Baker [1]. It is based on Heffter’s 1890 rotation system for $n=9$ [7], which she found in a paper by Moria Chas [2]. This model also has a “hexagonal” region, but one that twice uses the same vertex. This results in a map in which one country wraps around a toroidal arm and reuses one of its border vertices, forming a special valence-6 junction-point.

With the goal of obtaining overall $D_3$ symmetry, I investigated different embeddings of $K_9$ . By moving three of the vertices to the outer rim of the disk, I obtained a map with 20 triangular regions plus four quadrilaterals. Those quadrilaterals must map symmetrically onto themselves when one performs the flips around the three $C_2$ axes. In addition, the layout on the front and on the back would have to look the same. But most my efforts ended up in something like Figure 4(c), exhibiting just $C_3$ symmetry.

Sequin

(a)

(b) Figure 4: (a) Embedding of $K_9$ with one hexagonal region. (b) Ellie Baker’s first sewn model of $M_9$ [1]. (c) A different embedding of $K_9$ with three quadrilateral facets.

(c)

Eventually I found the layout shown in Figure 5(a). This layout first shows six quadrilateral regions, three of which must be split to accommodate the complete graph $K_9$ . These three edges, marked in black-and-white, could either lie on the front of the disk or on its backside, thus reducing the symmetry again down to $C_3$ . However, by placing such edges on both sides, one can obtain $D_3$ symmetry. The price one pays is that the graph $K_9$ now has three redundant edges, and the map $M_9$ (Figure 5(b,c)) has three pairs of countries with two segments of shared borders (running through two different holes). For other complete maps, it also turns out that a few redundant border lines can lead to an embedding with higher symmetry.

(a) Figure 5: $K_9$ and $M_9$ : (a) A redundant $D_3$ -symmetrical embedding of $K_9$ on a 3-hole torus; (b,c) $M_9$ , front & back. (Yellow and green touch in the top hole and in the left one).

(b)

(c)

Combinations of Simpler Maps, $n=10$

Several attempts to find a good layout of $K_{10}$ on a 4-hole torus, using the direct method that worked for $M_9$ , did not lead to a valid solution. A somewhat different approach starts with a smaller complete map and then adds some extra handles or tunnels to bring in additional colors. Starting with $M_9$ , we could add only a single handle which would then need to bring in one new color and connect it to all existing nine colors. I don’t see how this is possible without substantially rearranging the layout of the $M_9$ component.

Starting with $M_{\mathrm{B}}$ and adding two handles and two colors is more promising. The two handles can be combined into a single bridge with three branches, and this bridge then forms a genus-0 surface with three punctures. From these three punctures, three tubular connectors then must match up with three suitably placed punctures in the map $M_{\mathrm{B}}$ , so that all new, required, pair-wise country-connections are realized. This approach generalizes to a technique in which two maps with fewer countries and lower genus form a connected sum with the desired properties. Moira Chas and her students show how a complete map of lower genus can be enhanced by combining it with $b$ -way “branching bridges” to form a connected sum of higher genus [5]. Such an add-on bridge can be seen as a genus-0 surface with $b$ punctures, which can carry

Easy-to-Understand Visualization Models of Complete Maps

up to four additional countries with new colors. The $b$ open tubular ends of the branching bridge must then be inserted judiciously into the starting map so that all the new countries contact all the original countries in the starting map.

This approach leads to valid, tangible 3D models, where crocheted add-on bridges are stitched into crocheted handle-bodies. However, it is difficult to understand the resulting topology of such a model from just one or two pictures. To construct easy-to-visualize “pillowcase” representations, I need to do some extra work to place the add-on bridges into the dominant plane of the initial multi-hole disk — either by forming handles around the outer rim of the disk, or by inserting small “spidery” networks in some of the holes of the starting handle-body.

Based on the above approach, Eve Torrence [10] suggested starting with $M_8$ on a genus-2 surface and forming a connected sum with $M_2$ on a torus. In Figure 6(a,b), the torus is represented by the small white square, through which the blue and brown color regions connect with one another. Two connectors carrying both new colors connect to the top and bottom of the 8-country map shown in Figure 2(c,d), where there are valence-4 border points. At these two locations, the two new countries contact each of four countries in $M_8$ . Since the new component is a torus, we can wrap it around the $M_8$ component (Figure 6(c,d)).

(a,b)

(c,d)

(e,f) Figure 6: Back & front views of $M_{10}$ : (a,b) Connected sum between $M_8$ and a torus with 2 countries. (c,d) The same map redrawn with the torus wound around the $M_8$ component. (e,f) A connected sum between a torus with 6 countries and a genus-0, 4-way branching bridge with 4 countries.

More recently I found that I could make a valid 10-country map without redundant edges by starting with a 6-country torus and adding a 4-branch bridge with four new colors, where each branch carries three of those colors (Figure 6(e,f)). Finding this solution was not easy. I started from a map like the one shown in Figure 1(c), carrying the six colors (Pink, Cyan, Lime, Silver, Orange, Violet). For the connection points with the $M_4$ component I picked two valence-4 points and two valence-3 points, about equally spaced around the torus (Figure 7(a)). Next I had to pick the proper colors at those connection points, so that I obtain all $4\times 6=24$ color combinations between the $M_6$ and $M_4$ components (Figure 7(b)). Furthermore, I had to make sure that I could warp the $M_4$ component, which is a tetrahedron with four punctures at the corners, in the proper way to fit the four connectors in the proper sequence around the inner perimeter of the torus. A little paper-strip model helped in figuring out the right amount of twisting in the four connector tubes (Figure 7(c)).

(a) Figure 7: Connecting the $M_8$ and the $M_4$ components: (a) Selected connection points on the torus. (b) Choosing proper color matches. (c) Deformable tetrahedral frame to find the layout on $M_4$ .

(b)

(c)

Sequin

Given that I had to use two valence-4 points and two valence-3 points for the tie-in of the $M_4$ component, there is no hope for 4-fold rotational symmetry. But I was able to use the same layout on the front and on the back of the pillow-case model; so I was able to achieve at least $C_2$ symmetry around the vertical axis that flips the front into the back of this “pillow-case.”

A Tough Challenge, $n=11$

Among the complete maps that I have tried to model, $M_{11}$ presented the biggest challenge. I made several attempts to directly find an embedding of $K_{11}$ in a nice, symmetrical 5-hole torus, but none of them succeeded. Also, I had no example of a physical model made by crocheting or by stitching together eleven decagon patches. Thus, I focused on the topological approach of making a connected sum of two smaller complete maps. Moira Chas’ students, Y. Gu, C. Stewart, and A. Yamin [5] present a topological description based on the connected sum of $M_8$ on a genus-2 surface (Figure 8(a)) and $M_3$ on a sphere with four punctures (Figure 8(b)). This representation allows easy verification that all required color combinations occur along finite border lines. However, it does not convey a good visualization of the resulting handle-body with the 11 countries on its surface. Even a physical model in which I connected the $M_8$ component on top of a pillow-case model of $M_8$ (Figure 8(c)) does not give me a good picture of what the eleven countries drawn on a 5-hole torus would look like.

(a)

(b)

(c) Figure 8: (a,b) Topological model of $M_{11}$ [5]. (c) Paper model of $M_{11}$ on a genus-5 surface.

With the aim of creating a better visualization model, I first rearranged the map $M_8$ (Figure 8(a)) so that the four connection vertices all fall onto the perimeter of the folded pillow-case model of $M_8$ (Figure 9(a)). By further stretching the left half and compressing the right half, I was able to line up the two holes in the front and back sheets as well as the four connection points on the perimeter. Adding a suitably stretched and twisted layout of $M_3$ , provided all the needed color-pairings at the four connection points (Figure 9(b)).

(a) Figure 9: (a) Rearranged map $M_8$ to bring the four connection points to the periphery. (b) Adding a suitably stretched map of $M_3$ to obtain a pillowcase model of the $M_{11}$ .

(b)

Trying to find a more symmetrical layout, I looked at some other combinations of smaller complete maps — in particular, combinations of tori, with the hope to find a layout similar to Figure 6(e,f). Promising

Easy-to-Understand Visualization Models of Complete Maps

combinations are: either $M_7$ plus $M_4$ , or $M_6$ plus $M_5$ , on genus-1 surfaces with four connector tubes between them. I found a pleasing $D_4$ symmetrical layout for $M_4$ on a torus (Figure 10(a,b)), where every connector (Figure 10(c)) carries all four colors. So, I started my exploration with the latter model, using the same approach as in Figure 7. Now there are 14 valence-3 junction points to choose from. I am still struggling with this!

(a,b)

(d) Figure 10: (a,b) $M_4$ on a torus with four connectors (c). (d) Tool to help find the proper connections between the two tori with 4 and 7 countries, respectively.

A Symmetrical 3D Model, $n=12$

Almost twenty years ago, I found a symmetrical embedding of $K_{12}$ on a genus-6 surface that preserves the symmetry of an oriented tetrahedron [8]. The key step was to place the twelve nodes in twelve equivalent places with strongly negative Gaussian curvature (Figure 11(a)); this allowed the eleven edges going to other nodes to branch out without undue local congestion. I then made a physical model of a tubular genus-6 surface, onto which I could stick all 66 edges (Figure 11(b)). I now have made a corresponding computer graphics model of $K_{12}$ (Figure11(c)). To find the dual, $M_{12}$ , I picked twelve different colors for the nodes and recolored the edges as follows: each edge takes on the color of the node that it emerges from and keeps it up to the half-way point (Figure 11(d)); it then becomes a possible border point between two countries.

(a)

(b)

(c)

(d)

Figure 11: (a) Genus-6 handle-body with good node locations. (b) Symmetrical embedding of $K_{12}$ . (c) 66 edges of $K_{12}$ on polyhedral model. (d) Split edges, colored to show extent of 12 countries. (a)

(b) Figure 12: (a) Genus-6 handle-body with 12 differently colored countries. (b) One country singled out. (c,d) Two more views of map $M_{12}$ on a genus-6 handle-body with tetrahedral symmetry.

(c)

(d)

Séquin

Next, I repartitioned the surface of the polyhedral handle-body and matched the surface colors in all locations to the colors of the “roads” running through those areas (Figure 12(a)). Figure 12(b) shows a single country with all the graph half-edges emerging from that country’s “capital.” I then combined twelve copies of this one country into a single surface using the symmetry of the oriented tetrahedron. As a final test, I ran this combined surface through Stratasys’ Quickslice program to make sure that together they form the water-tight boundary representation of a handle-body. Figures 12(c, d) show the map $M_{12}$ with twelve identical countries after removal of the graph edges.

Conclusions, Future Work

For complete maps with more than seven countries it is not easy to convey the geometry of the handle-body and of the various countries with just one or two images. The pillowcase model is a useful representation. By showing front- and back-sides, it conveys all needed information. This also can be turned into simple physical model by printing out the two views and gluing them together. On such a model, it is easy to follow the geometries of convoluted countries that pass through any tunnels or wind around the perimeter.

Unfortunately, I have no general recipe how to find such pillowcase models. A few different approaches have been described that worked for maps with 8 to 11 countries. They will probably also work for maps with more than a dozen countries, although it may be difficult to predict which method works best for which map. An open question remains as to what the maximum possible symmetry might be for a particular complete map. Also, it seems worthwhile to find more structured techniques for combining smaller maps into the desired one. Is there a way to tell what combinations of maps will most likely succeed and lead to pleasing, symmetrical results?

Some maps, like $M_{12}$, are highly regular and can be embedded symmetrically on handle-bodies with the symmetry of one of the Platonic or Archimedean solids. For these maps it would be counter-productive to reduce the symmetry of the presentation to that of a 2-dimensional pillowcase. They may lead to informative and pleasing 3D-print models. But then, what would be the best way to convey the shape of an individual country in just one or two 2D images?

Acknowledgments

Zoom discussions and email exchanges with Ellie Baker, Moira Chas, Susan Goldstine, and Eve Torrence are greatly appreciated in the development of these models.

References

[1] E. Baker. “Sewn 9-country model.” Private communication, February 10, 2021. [2] M. Chas. “Crochet Topology.” AMS Feature Column, May 2018. – http://www.ams.org/publicoutreach/feature-column/fc-2018-05 [3] S. Goldstine. “Capturing Eight-Color Double-Torus Maps.” Bridges Conf. Proc. (2014). – https://archive.bridgesmathart.org/2014/bridges2014-377.html [4] S. Goldstine. “Eight Heptagons: The Double Torus Revisited.” Bridges Conf. Proc. (2020). – http://archive.bridgesmathart.org/2020/bridges2020-413.html [5] Y. Gu, C. Stewart, A. Yamin. “Maximally Complete Maps on Orientable Surfaces.” Draft, March 26, 2022. [6] P. J. Heawood. “Map colour theorem.” Journal of Pure and Applied Mathematics, No 24, pp 332-338, 1890. [7] L. Heffter. “Ueber ds Problem der Nachbargebiete.” Mathematische Annalen (1891). Vol: 38, page 477-508. [8] C. H. Séquin and L. Xiao. “$K_{12}$ and the Genus-6 Tiffany Lamp.” Proc. ISAMA CTI 2004, pp 49–52, Chicago, June. 17-19, 2004. [9] E. Torrence. “From $M_0$ to $M_{10}$.” Private communication, March 2022. [10] E. Torrence. “Modular Origami Map Coloring Models.” Bridges Conf. Proc. (2022). – https://archive.bridgesmathart.org/2022/bridges2022-507.pdf [11] E. Torrence. “Modular Origami Models of Complete Maps.” Mathematical Art Gallery at JMM 2023. – http://gallery.bridgesmathart.org/exhibitions/2023-joint-mathematics-meetings/etorrenc