Sand Drawings and Gaussian Graphs

Year: 2006 Authors: Erik D. Demaine; Martin L. Demaine; Perouz Taslakian; Godfried T. Toussaint

Core claim

Sand drawings can be modeled as Gaussian graphs, revealing new mathematical questions about their structure and realizability.

Topics

ethnomathematics, sand drawings, Gaussian graphs, planar maps, open problems

Domains

graph theory, topology, combinatorics, planar graph theory, cultural visual art, pattern design, kolam, sona

Methods

geometric abstraction, graph-theoretical analysis, planar embedding, combinatorial classification

Media

sand, powder, rice flour, floor drawings

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.

Erik D. Demaine Martin L. Demaine

Computer Science and AI Laboratory

Massachusetts Institute of Technology

{edemaine,mdemaine}@mit.edu

Perouz Taslakian

SOCS

McGill University

perouz@cs.mcgill.ca

Godfried T. Toussaint

SOCS & CIRMMT

McGill University

godfried@cs.mcgill.ca

Abstract

Sand drawings form a part of many cultural artistic traditions. Depending on the part of the world in which they occur, such drawings have different names such as sona, kolam, and Malekula drawings. Gaussian graphs are mathematical objects studied in the disciplines of graph theory and topology. We uncover a bridge between sand drawings and Gaussian graphs, leading to a variety of new mathematical problems related to sand drawings. In particular, we analyze sand drawings from combinatorial, graph-theoretical, and geometric points of view. Many new mathematical open problems are illuminated and listed.

1. Introduction

Different cultures around the world contain mathematics in one form or another. Not all of these mathematical ideas have developed out of necessity, like counting and calculation: some mathematical ideas are developed in the context of cultural arts. The study of this mathematical art within and without its cultural context constitutes the field of ethnomathematics [2, 3, 12, 22].

In this paper, we explore the mathematics and geometry found in a particular kind of visual art that seems to have developed independently in different forms in disparate cultures. In its basic form, the artist draws dots and one surrounding continuous loop, which crosses itself repeatedly, in the sand or on a floor sprinkled with powder. Collectively, we refer to these practices as sand drawings, though each practicing culture has its own name for the visual art.

For example, the women in Tamil Nadu (South India) create geometric designs using rice flower, called kolam, at the entrances of their homes [3]. One type of kolam, called pulli kolam, consists of first drawing a grid of dots (the pulli), and then drawing a continuous closed curve that partitions the planar space into as many bounded regions as there are dots, such that each bounded region contains exactly one dot. Each kolam drawing has a name. Figure 1 illustrates two such drawings.

Figure 1: Two examples of pulli kolam: the Anklet of Krishna (left) and The Ring (right).

Figure 2: Two examples of sona: the Antelope’s Paw (left) and the Spider (right).

The Tshokwe people of the West Central Bantu area of Africa make similar drawings called sona. In these drawings, it may happen that some regions contain more than one dot, or that some regions are empty [2, 12]. Figure 2 shows two such drawings: the drawing on the left has two empty bounded regions, while the drawing on the right has one bounded region with five dots. Some sona drawings do not have dots at all. However, in most sona drawings, there is exactly one dot per region.

Paulus Gerdes [12] has developed several geometric algorithms for constructing some families of sona drawings. One such algorithm uses Euclid’s algorithm for computing the greatest common divisor of two natural numbers. It is interesting that the Euclidean algorithm [9] not only generates traditional drawings in visual art, but also traditional rhythms in music [19].

In other traditions, people make drawings on the sand without first placing a grid of dots. The Malekula sand drawings are one such example. The Malekula people live on the island of Vanuatu in the South Pacific. Marcia Ascher [4] has analysed these drawings from the graph theoretic, geometric, and topological points of view.

From a geometric perspective, a sand drawing can be viewed as a self-intersecting closed curve drawn in the two-dimensional plane. Translating this definition of sand drawings into graph theory, the intersection points of the curve map to vertices and the portions of the curve connecting these vertices map to edges of a planar map. We are also interested in how dots can be placed so that exactly one dot lies in each region of the planar map (except for the infinite outside face). Although not all sand drawings have this property, this seems to be the most natural mathematical abstraction of the majority of sand drawings.

In this paper we unveil the bridge between sand drawings and a class of graphs known as Gaussian graphs. We pose a variety of basic questions about sand drawings and Gaussian graphs, solve some of them, and leave the reader with many interesting mathematical problems to consider.

2 Gaussian Graphs

Gaussian graphs implicitly go back to an observation of Carl Gauss around 1830 [11] that was proved by Julius v. Sz. Nagy almost a hundred years later [21]. The formal notion of Gaussian graphs was introduced more recently by Michael Gargano and John Kennedy [10], and then generalized by John Kennedy and Brigitte and Herman Servatius [14]. We follow the latter, more general, definition here, although our main interest is in the original definition of Gargano and Kennedy.

First we need some basic terminology from graph theory. A graph is a collection of vertices (or points) together with a collection of edges (or lines) connecting pairs of vertices. The degree of a vertex is the number of edges incident to it. A circuit in a graph is a cyclic sequence alternating between vertices and edges such that the two endpoints of each edge are the two adjacent vertices in the sequence. Thus a circuit may repeat vertices and/or edges. A graph is Eulerian if it has a circuit visiting every edge exactly once. It is well known that a graph is Eulerian if and only if it is connected and every vertex has even degree. A special family of Eulerian graphs is $4$-regular graphs, in which every vertex has degree exactly $4$. A planar map is a graph together with a planar embedding, a placement of the vertices as points in the plane and a drawing of the edges as curves that intersect each other only at common endpoints. When such a planar embedding exists, the graph itself is also called planar. A planar graph can have several different planar embeddings. We call two planar embeddings (combinatorially) equivalent if they define the same clockwise cyclic order of edges around each vertex.

Intuitively, a Gaussian graph [14] is a planar map that can be drawn by a single closed curve that “goes straight” at each vertex. More precisely, two edges incident to a common vertex $v$ are parallel if these edges partition the clockwise order of edges around $v$ into two pieces with an equal number of edges. In other words, if we label the edges incident to $v$ by $1,2,\dots ,\mathrm{degree}(v)$ in clockwise order, then two of these edges are parallel precisely if they have the same label modulo $\mathrm{degree}(v)/2$. A transverse circuit of a planar map is a circuit whose successive edges are parallel. A planar map is Eulerian if and only if it is connected and its

edges decompose into one or more transverse circuits. A Gaussian map is an Eulerian map that decomposes into exactly one transverse circuit.

Intuitively, a sand drawing or sona drawing is a closed curve drawn in the plane such that no more than two pieces of the curve intersect at the same point and such that the curve does not “touch” itself without crossing itself. More precisely, if we label the four portions of the curve around an intersection point $v$ by $1,2,3,4$ in clockwise order, then the curve in a sona drawing should connect portion $1$ to portion $3$, connect portion $2$ to $4$, and connect no other pairs. In other words, a sona drawing is a $4$-regular Gaussian map, so we also use the term sona map to make clear the underlying graph and embedding structure. Kennedy et al. [14, Theorem 2] show that, for any 4-regular planar graph, the number of its transverse circuits is independent of its embedding. Thus, all embeddings of the underlying graph in a sona map are sona maps. We can therefore define a sona graph to be a planar 4-regular graph whose planar embeddings (all) create sona maps.

There are efficient (linear-time) algorithms to determine whether a given graph or map are sona. To decide whether a planar map is sona, check 4-regularity and check whether all edges are visited by starting on an arbitrary edge $e_0$ in an arbitrary orientation and, upon entering a vertex $v$ along an edge $e$, exiting $v$ along the unique edge incident to $v$ that is parallel to $e$. Kennedy et al. [14] give an incremental characterization of all sona maps, which also leads to an efficient algorithm for deciding whether a planar map is sona. To decide whether a graph is sona, find a planar embedding using, e.g., the algorithm of [6], and upon success, test whether the resulting planar map is sona as above.

Throughout this paper, $n$ denotes the number of bounded regions or faces of a sona map, or the number of such regions that a sona graph would have if it were embedded into the plane. This count $n$ corresponds to the number of dots that would be placed, exactly one per bounded face, in many cultural practices. We therefore sometimes speak of “a sona map on $n$ dots” or “a sona graph on $n$ dots”.

Lemma 1

A sona graph on $n$ dots has $n-1$ vertices and $2(n-1)$ edges.

Proof: The number $E$ of edges is half the total degree of the $V$ vertices. Because every vertex has degree $4$, $E=2V$. By Euler’s Formula, $V-E+F=2$ where $F=n+1$ is the number of faces including the infinite outside face. Substituting $E$ and $F$, we obtain $V-2V+n+1=2$, i.e., $V=n-1$. Therefore, $E=2V=2(n-1)$. $\square$

In addition to their connection to Gaussian graphs in graph theory, sona maps are equivalent to generic closed curves (immersions of the unit circle into the plane) in the field of topology. By generic, we mean that the curve is not tangent to itself anywhere and that no more than two portions of the curve cross at any point. Arnol^{′}d [1], for example, proves several topological invariants about such curves. Craveiro [7] considers the curves that are “maximally looped”. Ozawa [17] considers the number of bitangents, shared tangents between different points on the curve.

3 Combinatorics of Sand Drawings

In this section, we analyze the number of different sona drawings. There are two main different objects we can count: sona graphs and sona maps. Each sona graph has one or more associated sona maps, so in general there are more maps than graphs.

3.1 Enumeration and Drawing.

We have developed a software program that generates all sona graphs and sona maps on $n$ dots, for small $n$. More precisely, the program generates all distinct sona graphs on $n$ dots, and all distinct sona maps on $n$ dots, incrementally for $n=2,3,4,\dots$. It uses the incremental characterization of sona maps by Kennedy et al. [14] to generate, for each sona map on $n-1$ dots, a list of $O(n^2)$ sona maps on $n$ dots. The combined list of all such sona maps on $n$ dots includes all possible sona maps on $n$ dots, but it lists the same sona map more than once if it can be generated in multiple ways. The

time consuming part of the computation is to then remove duplicates from the resulting list, first according to combinatorial equivalence of sona maps, and second according to isomorphism of sona graphs. The program simply tests each pair of sona maps for equivalence of either type, by testing all possible bijections between the vertices of the two maps, and removes duplicates.

Table 1 shows the computed number of sona graphs and sona maps on $n$ dots for $n$ between 1 and 8.

The program also draws a polygonal planar embedding of each sona map, where each edge is represented by a chain of up to three line segments, by triangulating and applying a theorem of Tutte [20]. Unfortunately, these drawings make poor use of area and are barely visible without zooming in extremely close. We redrew each sona map for $n$ between 1 and 4 using a combination of circular arcs and straight lines, joined at common tangents, so that the resulting curve always crosses itself at right angles, and to illustrate all symmetries in the map. Figure 3 shows these drawings of all sona maps for $n$ between 1 and 4.

We distinguish sona maps from their reflections, but the only sona map in Figure 3 that lacks reflectional symmetry is the second and fourth maps in the second row of $n=4$ , which resemble a treble clef.

Table 1: Number of sona graphs and sona maps on $n$ dots for small $n$ .

3.2. Combinatorial Complexity. One measure of the combinatorial complexity of a sona map on $n$ dots is the sum of the depths of all its faces; the depth of a face is the minimum number of edges that a point within the face needs to cross in order to reach the outer face of the map. For $n=4$ , the sona map with the highest complexity is the third map on the second row of $n=4$ in Figure 3. It consists of a loop nested within double edges and a loop, resembles a rose, and has complexity 10. The face depth sequence of a sona map is the ordered sequence of the depths of all its bounded faces. The face depth sequence does not uniquely define a sona map. For example, the two rightmost maps on the first row of $n=4$ in Figure 3 have the same face depth sequence 1, 1, 2, 2.

3.3. Sona Maps. The general combinatorics of sona maps remains open:

Open Problem 1 How many different sona maps are there on $n$ dots?

This question has been studied before for small $n$ by Arnol’d [1]. The sequence is in OEIS [18, A008981]. The rightmost column of Table 1 shows the sequence for small $n$ , computed by Arnol’d [1] and verified exhaustively by our software. To our knowledge, however, no closed-form solution or asymptotic bounds have been published previously. Again we can provide asymptotic upper and lower bounds of $2^{\Theta (n)}$ :

Theorem 2 There are at least $\Omega (4^n/n^{3/2})$ different sona maps on $n$ dots.

Proof: As defined by Arnol’d [1], a sona map is tree-like if cutting any vertex disconnects the map into two components. For example, the top-right map of $n=4$ in Figure 3 is not tree-like, while the one to its left is tree-like. Every rooted ordered tree can be converted into a different tree-like sona map, so the number of such sona maps is at least the number of rooted ordered trees. The number of such trees on $n$ nodes is the $n$ th Catalan number: $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/(n+1)=\frac{1}{\sqrt{\pi }}{4}^n/n^{3/2}-O(4^n/n^{5/2})$ .

Theorem 3 There are at most $16^{n-O(\lg n)}$ different sona maps on $n$ dots.

Figure 3: All sona maps on $n$ dots for $n$ between 1 and 4.

Proof: The number of sona maps on $n$ dots is at most the number of Eulerian planar maps on $n^{\prime }=2(n-1)$ edges. This sequence is in the OEIS [18, A069727]. Liskovets and Walsh [15] give an explicit formula for this sequence. Also they prove that the number of Eulerian planar maps on $n^{\prime }$ edges is asymptotically equal to the number of rooted Eulerian planar maps on $n^{\prime }$ edges divided by $2n^{\prime }$ , while the number of rooted Eulerian planar maps on $n^{\prime }$ edges is

Therefore, the number of sona maps on $n$ dots is asymptotically at most $16^{n-O(\lg n)}$ .

3.4. Sona Graphs. The general combinatorics of sona graphs also remains open:

Open Problem 2 How many different sona graphs are there on $n$ dots?

Figure 4: Two different sona maps with the same face degree sequence: 1, 1, 4, 5.

Figure 5: A sona map in which all but two faces have degree 1.

The middle column of Table 1 shows the answer for small $n$ , found via exhaustive search. This sequence is not currently listed in the On-line Encyclopedia of Integer Sequences (OEIS) [18], and we plan to submit it. While the exact counts remain open for general $n$ , we can provide asymptotic upper and lower bounds of $2^{\Theta (n)}$ :

Theorem 4 There are at least $\Omega (2.95^n)$ different sona graphs on $n$ dots.

Proof: As in the proof of Theorem 2, we consider tree-like sona maps. Every unrooted unordered tree can be converted into a different tree-like sona graph, so the number of such sona graphs is at least the number of unrooted unordered trees. The latter sequence is in the OEIS [18, A000055]. Otter [16] computes the asymptotic number of unrooted unordered trees on $n$ vertices to be $\frac{{\beta }^3}{3{\alpha }^{9/2}}\left|\left(\genfrac{}{}{0ex}{}{3/2}{n}\right)\right|{\alpha }^n+O({\alpha }^n/n^{7/3})\approx 0.53479{\alpha }^n/n^{5/2}+O({\alpha }^n/n^{7/2})$ , where $\alpha \approx 2.955765$ and $\beta \approx 7.924$ .

Our best upper bound on the number of sona graphs follows trivially from Theorem 3’s upper bound on the number of sona maps:

Corollary 5 There are at most $16^{n-O(\lg n)}$ different sona graphs on $n$ dots.

We are not aware of any better upper bounds on the number of Eulerian planar graphs compared to what we used in Theorem 3 about Eulerian planar maps. For example, the best known asymptotic upper bound on the number of unlabeled planar graphs with $n$ vertices is given by Bonichon et al. [5]: $2^{\alpha n+O(\log n)}$ where $\alpha \approx 4.9098$ . This result implies an upper bound of $O(30.1^n)$ , which is strictly worse than Corollary 5.

4. Face Degrees of Sand Drawings

This section investigates the “face degree sequence” of sona maps. The degree of a face in a planar map is the number of edges that bound the face. The face degree sequence of a planar map is the sequence of the degrees of all bounded faces (excluding the infinite outside face), sorted by degree. There can be multiple sona maps with the same face degree sequence. Figure 4 shows one such example.

We omit the degree of the outside face from the face degree sequence because it is determined by $n$ and the rest of the sequence. The total degree of all faces, including the outside face, is twice the number of edges. By Lemma 1, the degree of the outside face is $4(n-1)$ minus the total degree of all bounded faces, i.e., the sum of the values in the face degree sequence.

4.1. Equal Face Degrees. We begin by investigating the extent to which most of the degrees in the face degree sequence can be equal. First we prove that most of the face degrees are equal, they must be at most 4:

Lemma 6 The average face degree of any sona map, counting the outside face, is $4(n-1)/(n+1)=4-8/n+O(1/n^2)$ .

Figure 6: A sona map in which all but three faces have degree exactly 2.

Figure 7: “Men-lions that, stealthily, plan their intrigues” [12].

Proof: Let $D$ denote the average face degree. The number of edges is half the total face degree: $E=(DF)/2$ . By Lemma 1, $2(n-1)=(D(n+1))/2$ , so $D=4(n-1)/(n+1)$ . Asymptotically, $(n-1)/(n+1)=1-2/n+2/n^2-O(1/n^3)$ .

Lemma 7 For any $n$ , there is a sona map on $n$ dots with $n-1$ faces of degree exactly 1.

Proof: See Figure 5. The construction loops around each of the $n$ dots in turn. For the last dot, however, it just circles around it and connects to the starting point.

Lemma 8 For any $n$ , there is a sona map on $n$ dots with $n-2$ faces of degree exactly 2, and with two faces of degree exactly 1.

Proof: See Figure 6. The construction takes a loop of string and twists the two strands (reversing their order) in between passing over each dot.

Interestingly, this construction appears as an element in real-world sona drawings; see Figure 7.

Lemma 9 For any $n$ , there is a sona map on $3n+1$ dots with $3n-2$ faces of degree exactly 3, and with two faces of degree exactly 2.

Proof: See Figure 8. Take the construction from Figure 6 and, just before closing the loop, continue the drawing by crossing each face, dividing each face into two; then return to the original point to close the loop.

Lemma 10 For any $n$ , there is a sona map on $n$ dots with $n-O(\sqrt{n})$ faces of degree exactly 4.

Proof: See Figure 9. Consider the “grid” sona map where all faces except for $O(\sqrt{n})$ on the boundary have degree exactly 4. Now, for any such grid sona map with $n$ faces, we can draw a grid sona map with a higher value of $n$ by adding two rows or two columns, whichever is smaller. The total number of faces added to the new drawing is at most $2\sqrt{n}$ . Thus, the gap in the number of faces between any two consecutive grid sona maps is $O(\sqrt{n})$ . To construct a sona map whose number of faces is between $n$ and $n+2\sqrt{n}$ , we can simply pick a non-degree-4 face and add loops to the face until we obtain the number of faces we want. This modification changes the degree of one face and will add up to $O(\sqrt{n})$ new faces, thus keeping the number of faces not of degree 4 bounded by $O(\sqrt{n})$ .

This construction also appears in real-world sona drawings; see Figure 10. A similar grid-like construction appears in the pulli kolam of Figure 1.

Figure 8: A sona map in which all but four faces have degree exactly 3.

Figure 9: A sona map with $n-O(\sqrt{n})$ faces of degree exactly 4.

Figure 10: “A small animal that lives in a tree hole and pierces the intestines” [2].

4.2. Characterizing Face Degree Vectors.

Open Problem 3 What is the complexity of deciding whether a given finite nondecreasing sequence of positive integers is the face degree sequence of some sona map? When it exists, can we construct such a sona map?

An obvious necessary condition for a finite sequence of positive integers to be the (vertex or face) degree sequence of a graph is that the sum must be even (twice the number of edges). Hakimi [13] proved that every such sequence is the vertex degree sequence of some graph, possibly with loops and multiple edges. Note that this problem is substantially easier than characterizing the degree sequences of simple graphs (with no loops or multiple edges), considered by Erdős and Gallai [8] and Hakimi [13].

Naturally, this universality no longer holds when we add the restrictions of planarity, Eulerian, Gaussian, and/or sona. One specific related problem, which we are not aware of being studied before, is the following:

Open Problem 4 What is the complexity of deciding whether a given finite nondecreasing sequence of positive integers is the (vertex or face) degree sequence of some planar map? When it exists, can we construct such a planar map?

Face and vertex degree sequences are closely related to face depth sequences defined in Section 3.2: all three are integer sequences that do not uniquely define a sona map. Thus, the open problems of this section can also be asked for face depth sequences.

5. Sand Drawings on Given Dots

In this section, we consider a family of geometric sand-drawing problems: given $n$ dots in the plane, find a sona map with exactly one of the given dots in each face (except the outside face) subject to some constraints or optimizing some objective function. This extra constraint captures how sand drawings are often performed in practice.

5.1. Minimum-Length Sona Maps. A natural geometric objective, albeit of dubious artistic merit, is to minimize the Euclidean length of the curve (or equivalently, the total Euclidean length of edges in the map). This minimum length is in fact an infimum, and may not be exactly achievable.

Open Problem 5 What is the complexity of finding the minimum-length sona map for a given set of dots in the plane?

A natural value to compare to is the minimum length of a Euclidean Traveling Salesman (TSP) tour, i.e., the shortest closed tour that visits every dot. We refer to the length of this tour as TSP.

Lemma 11 For any \varepsilon >0 , every set of dots has a sona map of length $\mathrm{TSP}+\epsilon$ .

Proof: As in the proof of Lemma 7 and Figure 5, we loop around each dot in turn, now with very small loops, connecting the loops together with the TSP tour. We do not loop around the last dot, but we do visit it to ensure that it is enclosed by the high-degree bounded face. $\square$

Lemma 12 There is a set of four dots on which the minimum-length sona map has length $\mathrm{TSP}/c_0$ where c_{0} = 2 / 3 + 2\sqrt{3} /9 > 1.05 .

Proof: Consider four dots, three dots forming an equilateral triangle with side length 1 and the fourth dot in the center of the triangle (Figure 11). The optimal TSP tour has length 2 + 2\sqrt{3} / 3 > 3.15 , while the optimal solution visits only the corners of the triangle, at a cost of $3+\epsilon$ for some small positive $\epsilon$ .

Open Problem 6 Does every sona map have length at least $\mathrm{TSP}/c$ for some constant c > 0 ?

5.2. Other Objectives. Geometrically, it is natural to consider optimizing objectives other than total Euclidean length. It remains to determine whether these objectives are artistically more or less interesting.

Figure 11: The TSP tour (dashed lines) is slightly longer than the sona map whose faces encircle the given dots.

Open Problem 7 What is the complexity of finding a sona map on a given set of dots, where each edge is drawn as a polygonal chain of links, that minimizes the total number of links?

Open Problem 8 What is the complexity of finding a sona map on a given set of dots that minimizes the total absolute turn angle along the transverse circuit?

5.3. Two Coloring. A more difficult family of problems arises when each dot has one of two colors, and the face 2-coloring of the sona map must match the specified coloring of dots. We can extend Lemma 11 to this case:

Lemma 13 For any \varepsilon >0 , every 2-colored set of dots has a sona map of length $\mathrm{TSP}+\epsilon$ .

Proof: See Figure 12. We follow the proof of Lemma 11, but loop right or loop left around each dot according to color. The last dot is in the high-degree face; if it has the wrong color, invert all of the other dots’ orientations to fix it. $\square$

5.4. Clockwise Turning.

Open Problem 9 Given a sona map, can we decide in polynomial time whether it can be drawn using only clockwise turns? Characterize such sona maps. How many are there on $n$ dots?

It is not the case that every face degree vector of a sona map is the face degree vector of a clockwise-turning sona map. A simple example is the sona drawing illustrated in Figure 13 whose face degree vector has nine 1’s and one 10. Another interesting question is whether the family of sona maps with face degree vector $1,1,\dots ,1,k+1$ , where the number of 1’s is k > 1 , constitutes a family of sona maps that cannot be drawn with only clockwise turns.

Figure 12: Given dots colored as either circles or squares, we can always find a sona map in which no two faces containing elements of the same color share an edge.

Figure 13: This sona map with face degree vector 1, 1, 1, 1, 1, 1, 1, 1, 1, 10 cannot be drawn with only clockwise turns.

References

[1] V. I. Arnol’d. Topological Invariants of Plane Curves and Caustics. American Math. Soc., 1994. [2] M. Ascher. Ethnomathematics: A Multicultural View of Mathematical Ideas. Chapman and Hall, 1998. [3] M. Ascher. Mathematics Elsewhere: An Exploration of Ideas Across Cultures. Princeton, 2002. [4] M. Ascher. Malekula sand tracings: A case in ethnomathematics. In Proceedings of BRIDGES: Mathematical Connections in Art, Music and Science, pages 57-64, Banff, Canada, 2005. [5] N. Bonichon, C. Gavoille, N. Hanusse, D. Poulalhon, and G. Schaeffer. Planar graphs, via well-orderly maps and trees. In Proc. 30th Int. Workshop Graph Th. Concepts Comp. Sci., pp. 270-284, 2004. [6] J. M. Boyer and W. J. Myrvold. On the cutting edge: simplified $O(n)$ planarity by edge addition. Journal of Graph Algorithms and Applications, 8(3):241-273, 2004. [7] F. J. C. de Carvalho. Characterizing maximally looped closed curves. Amer. Math. Monthly, 92(3):202-207, 1985. [8] P. Erdős and T. Gallai. Graphs with prescribed degrees of vertices. Mat. Lapok, 11:264-274, 1960. [9] P. Franklin. The Euclidean algorithm. Amer. Math. Monthly, 63(9):663-664, 1956. [10] M. L. Gargano and J. W. Kennedy. Gaussian graphs and digraphs. In Proc. 25th Southeastern Int. Conf. Combinatorics, Graph Theory and Computing, Congressus Numerantium 101:161-170, 1994. [11] C. F. Gauß. Zur Geometrie der Lage für zwei Raumdimensionen. In Werke (Collected Works), volume 8, pages 282-286. Springer-Verlag, 1990. [12] P. Gerdes. Geometry From Africa: Mathematical and Educational Explorations. MAA, 1999. [13] S. L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. I. SIAM Journal on Applied Mathematics, 10:496-506, 1962. [14] J. Kennedy, B. Servatius, and H. Servatius. A note on gaussian graphs. Congressus Numerantium, 112:112-117, 1995. [15] V. A. Liskovets and T. R. S. Walsh. Enumeration of eulerian and unicursal planar maps. Discrete Math., 282(1-3):209-221, May 2004. [16] R. Otter. The number of trees. Annals of Mathematics, 49:583-599, 1948. [17] T. Ozawa. On Halpern’s conjecture for closed plane curves. Proc. AMS, 92(4):554-560, 1984. [18] N. Sloane. On-line encyclopedia of integer sequences. http://www.researchAtt.com/~njas/sequences/. [19] G. T. Toussaint. The Euclidean algorithm generates traditional musical rhythms. In Proceedings of BRIDGES: Mathematical Connections in Art, Music and Science, pages 47-56, Banff, Canada, 2005. [20] W. T. Tutte. How to draw a graph. Proc. London Math. Soc., Series 3, 13:743-767, 1963. [21] J. v. Sz. Nagy. Über ein topologisches Problem von Gauß. Math. Zeit., 26(1):579-592, 1927. [22] C. Zaslavsky. Africa Counts: Number and Pattern in African Cultures. Lawrence Hill Books, 1999.