¿^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 309-337 https://doi.org/10.26493/1855-3974.2006.fa4
(Also available at http://amc-journal.eu)
Simultaneous current graph constructions for minimum triangulations and complete graph
embeddings
Timothy Sun * ©
Columbia University, New York, NY, USA
Received 15 May 2019, accepted 18 January 2020, published online 21 October 2020 Abstract
The problems of calculating the genus of the complete graphs and of finding a minimum triangulation for each surface were both solved using the theory of current graphs, and each of them divided into twelve different cases, depending on the residue modulo 12 of the number of vertices. Cases 8 and 11 were of particular difficulty for both problems, with multiple families of current graphs developed to solve these cases. We solve these cases, in addition to Cases 6 and 9, in a unified manner, greatly simplifying previous constructions by Ringel, Youngs, Guy, and Jungerman. All these new constructions are index 3 current graphs sharing nearly all of the structure of the simple solution for Case 5 of the Map Color Theorem.
Keywords: Topological graph theory, current graphs, map coloring, triangulations. Math. Subj. Class. (2020): 05C10, 05C15
1 Introduction
In this paper, we only consider surfaces which are orientable. We let Sg denote the surface of genus g, i.e., the sphere with g handles. The Heawood number of the orientable surface Sg of genus g,
H(Sg ) = ^^^
gives rise to two distinct problems which share many similarities. On one hand, the Hea-wood number is an upper bound on the chromatic number of the surface, and the celebrated Map Color Theorem of Ringel, Youngs, and others [17] proves that this inequality is tight
»The author was partially supported by NSF grants CCF-1420349, CCF-1563155, and CCF-1703925. E-mail address: timothysun@sfsu.edu (Timothy Sun)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
309
Ars Math. Contemp. 18 (2020) 187-210
(after rounding the Heawood number to the nearest integer) for all surfaces of genus g > 1 by determining the genus of the complete graphs. In the reverse direction, H(Sg) is a lower bound on the minimum number of vertices needed to triangulate the surface with a simple graph. For g > 1, g = 2, this was also shown to be tight by Jungerman and Ringel [11].
Both of these problems break down into twelve cases, where "Case k" refers to the relevant graphs on 12s + k vertices. The main tool for constructing most of the required embeddings is the theory of current graphs [ ]. At times, there is overlap—for example, the complete graph K7 triangulates the torus, thereby demonstrating that the chromatic number of the torus and the smallest number of vertices needed to triangulate the torus is 7. However, many of the cases are solved separately, and furthermore, Jungerman and Ringel's [11] solution for the latter problem of minimum triangulations1 often required multiple unrelated families of current graphs.
Our goal is a partial unification of both problems using index 3 current graphs, i.e., current graphs whose embeddings have three faces. The standard solutions for Cases 3 and 5 of the Map Color Theorem, i.e., the genus of the complete graphs on 12s+3 and 12s+5 vertices, respectively, used simple families of index 3 current graphs whose origins can be traced back to constructions for Steiner triple systems. However, other constructions employing index 3 current graphs, perhaps most notably Case 6 of the Map Color Theorem (see §9.3 of Ringel [16]), have not realized the same level of simplicity. For each of Cases 6, 8, 9, and 11, we present a single family of current graphs which solves both the complete graph and minimum triangulation problems except for a few small-order graphs or surfaces. Not only do these constructions improve upon past solutions in the literature, but the structure of the current graphs for the general case reuses all but a fixed part of the aforementioned current graphs used for Case 5.
2 Embeddings in surfaces and the Heawood numbers
For background in topological graph theory, see Gross and Tucker [3]. In a graph, possibly with self-loops or parallel edges, every edge has two ends that are each incident with a vertex. A rotation of a vertex is a cyclic permutation of its incident edge ends, and a rotation system of a graph is an assignment of a rotation to every vertex of the graph. The Heffter-Edmonds principle states that cellular embeddings of a graph are in one-to-one correspondence with rotation systems: each embedding in a surface defines a rotation system by considering the cyclic order of the edge ends emanating at each vertex, while in the reverse direction, the faces of the embedding can be traced out from the rotation system in a unique manner. Our convention will be that rotations define clockwise orderings, which induce counterclockwise orientations for faces. In the case of simple graphs, one can express a rotation in terms of the vertex's neighbors, so a rotation system can be represented as a table of vertices, where each row corresponds to a cyclic permutation of the neighbors of a specific vertex.
The Euler polyhedral formula states that for a cellular embedding ^: G ^ Sg, we have the expression
|V(G)| - |E(G)| + IF(G,^)| = 2 - 2g,
where g denotes the genus of the surface and F(G, is the set of faces induced by the embedding. A standard consequence is the following inequality:
1 Jungerman and Ringel [11] used the term minimal triangulations.
T. Sun: Simultaneous current graph constructions
311
Proposition 2.1. Let $: G ^ Sg be an embedding of a simple, connected graph G with at least 3 vertices. Then
|E(G)| < 3|V(G)| — 6 + 6g,
where equality is achieved when the embedding is triangular, i.e. when all its faces are triangular.
The (minimum) genus of a graph G is the minimum genus over all cellular embeddings of G, and is denoted y (G). A (minimum) genus embedding of G is an embedding whose genus achieves this minimum.
Corollary 2.2. For a simple, connected graph G with at least 3 vertices, its genus is at
least	_	_
(G)| — 3|V (G)| + 6"
Y (G) >
6
We say that an embedding of a simple graph is triangle-tight if its genus equals this lower bound. If a triangle-tight embedding exists, it must necessarily be of minimum genus. From these relationships between the edge and vertex counts and the genus, one can derive the Heawood number	_
h =
of the surface Sg, which serves as a rough measure of "maximum possible density" in the following two inequalities:
Proposition 2.3 (see Ringel [16, p. 63]). For g > 1, the chromatic number x(Sg) of the surface Sg, i.e., the maximum chromatic number over all graphs embeddable in Sg, satisfies
X(Sg ) < L H (Sg )J .
Let MT (Sg) be the minimum number of vertices over all simple graphs G that have a triangular embedding in Sg.
Proposition 2.4 (Jungerman and Ringel [11]). For each surface Sg with g > 1,
MT (Sg ) > \H (Sg )! .
Such an embedding in Proposition 2.4 is known as a minimum triangulation of Sg. We call a triangular embedding of a graph an (n, t)-triangulation if the graph has n vertices and (2) — t edges, i.e. the graph is the complete graph on n vertices with t edges deleted. The tightness of the inequalities in Propositions 2.3 and 2.4 is proven via alternative formulations that emphasize the number of vertices:
Theorem 2.5 (Ringel and Youngs [17]). The genus of the complete graph Kn is
' (n — 3)(n — 4)"
Y (Kn) =
12
Theorem 2.6 (Jungerman and Ringel [11]). For all pairs (n,t) of nonnegative integers n > 3, t < n — 6 satisfying
(n — 3)(n — 4) = 2t (mod 12), there exists an (n, t)-triangulation, except for (n, t) = (9, 3).
312
Ars Math. Contemp. 18 (2020) 187-210
Another way of stating Theorem 2.5 is that every complete graph Kn, n > 3, has a triangle-tight embedding. In both problems, the proof breaks down into several cases, depending on the residue of the number of vertices n mod 12. We call the subcase concerning graphs with n = 12s+k vertices Case k, for k = 0,1,..., 11, and we often reference the value s in our exposition. For example, if we speak of "Case 6, s = 2" of the Map Color Theorem, we are referring to the complete graph K30. To differentiate between the two problems, we refer to "Case k-CG" and "Case k-MT" to denote Case k of the Map Color Theorem ("complete graph") and minimum triangulations problem, respectively.
The fact that there are 12 Cases depending on the number of vertices for both the Map Color Theorem and the minimum triangulations problem suggests a connection between the solutions of the two problems. Indeed, in several Cases, the current graphs used in the proof [17] of the Map Color Theorem for Kn have the dual purpose of also providing all the necessary minimum triangulations on the same number of vertices n. However, not all Cases have been combined in this manner.
In general, our constructions will proceed in the following way: using an index 3 current graph, we generate an (n, t)-triangulation. We wish to find other embeddings of graphs on the same number of vertices using the following operations:
•	handle subtraction, which deletes edges from a triangular embedding to produce a triangular embedding on a lower-genus surface, and
•	additional adjacency, which adds edges using extra handles and other local operations.
By subtracting handles, we obtain all the necessary (n, t')-triangulations, for t' > t, and over the course of the additional adjacency step for constructing a triangle-tight embedding of Kn, we construct the remaining (n, t'')-triangulations, for t'' < t.
3 Outline for additional adjacencies
The main goal for our additional adjacency steps is to utilize as little information about the embeddings as possible. For this reason, we present the additional adjacency solutions first, before describing any current graphs. Like in previous work, our additional adjacency solutions make use of three different operations for adding a handle, which are described in Constructions 3.1, 3.2, and 3.8 in primal form. Most of these constructions are already known, except Proposition 3.6 and Lemma 3.10. In prose, we describe the modifications to the embeddings in terms of rotation systems, so their correctness can be checked by tracing the faces and applying the Heffter-Edmonds principle. Our drawings, on the other hand, describe an alternative topological interpretation using surgery on the embedded surfaces. While these operations work more generally, we assume that all graphs in this section are simple and their embeddings are triangular.
Construction 3.1. Modifying the rotation at vertex v from
v. xi ... Xi yi ... yj zi ... zk
to
v. xi ... Xi zi ... zk yi ... yj , as in Figure 1 increases the genus by 1 and induces the 9-sided face
[xi,zk,v, yi,Xi,v,zi,yj,v].
T. Sun: Simultaneous current graph constructions
313
Construction 3.2. Modifying the rotation at vertex v from
v. xi .. . Xi yi . .. yj zi .. . zk wi .. . w£
to
v. xi ... Xi wi ... w£ zi ... zk yi ... yj as in Figure 2 increases the genus by 1 and induces the two 6-sided faces
[xi,wz,v,zi,yj,v] and [wi, z^,v,yi,Xi,v\.

(a)
Vj (b)
Figure 1: Rearranging the rotation at vertex v (a) increases the genus and creates room (b) to add new edges.
Remark 3.3. While the drawings in Figures 1 and 2 are drawn asymmetrically, the operations are in fact invariant under cyclic shifts of the subsets x1,... ,xH; y1,..., yj, etc.
Several Cases of the Map Color Theorem are solved by first finding triangular embed-dings of Kn — K3. The first consequence of Construction 3.1 is to transform such an embedding into a genus embedding of a complete graph.
Proposition 3.4 (Ringel [15]). If there exists a triangular embedding of Kn — K3 in the surface Sg, then there exists a genus embedding of Kn in the surface Sg+1.
Before showing how this follows from the above constructions, we first argue that all the embeddings of complete graphs we construct are in fact of minimum genus.
Proposition 3.5. Suppose we have a triangular embedding of a graph Kn — He, where He is a graph on e edges, e < 6. If we add the missing e edges by using one handle, the resulting embedding of Kn is triangle-tight.
Proof. One can verify that the difference between the genus of Kn — He, as given by Proposition 2.1, and the genus of Kn is exactly 1.	□
Proof of Proposition 3.4. If the three nonadjacent vertices are a, b, c, pick any other vertex v and apply Construction 3.1 with xi = a, y1 = b, z1 = c. In the resulting nontriangular face, the nonadjacent vertices can be connected like in Figure 3(a).	□
x
314
Ars Math. Contemp. 18 (2020) 187-210


Vi w Vj wi
(a)
)xi y ic
(b)
Figure 2: Rearranging four groups of neighbors (a) yields two hexagonal faces (b).
For Cases 8 and 11, we will construct triangular embeddings of the graph Kn — K 1,4. These missing edges can be added in using one handle if the embedding satisfies an additional constraint:
Proposition 3.6. Let Kn — K14 be a complete graph with the edges (u, q1),..., (u, q4) deleted. If there exists a triangular embedding $: (Kn — K1,4) ^ Sg with a vertex v with rotation
v. ... qi q2 ... q3 q4 . ..,
then there exists a genus embedding of Kn in the surface Sg+1.
Proof. Note that vertices u and v are adjacent, so assume without loss of generality that u appears in the rotation of v in between q4 and q1. Apply Construction 3.1 with
Xi = q1, V1 = q2, Vj = q3, Z1 = q4, zk = u and connect the missing edges in the 9-sided face, as in Figure 3(b).
□
This constraint is relatively easy to satisfy, since there are a few possible permutations for q1,..., q4, in addition to the fact that v is an arbitrary vertex. In fact, when we only need to add back three edges, this is always possible:
Corollary 3.7 (Ringel et al. [ , 19]). If there exists a triangular embedding of Kn — K1,3 in the surface Sg, then there exists a genus embedding of Kn in the surface Sg+1.
Proof. One can always find such a vertex v by choosing a vertex on one of the triangles incident with, say, the edge (q1,q2).	□
v
v
v
v
T. Sun: Simultaneous current graph constructions ...
315
(a)	(b)
Figure 3: Two possibilities for adding edges after invoking Construction 3.1: a K3 subgraph (a), and a Ki<4 subgraph (b).
A third type of handle operation is to merge two faces with a handle without modifying the rotations at any vertices. To do this, we excise a disk from two faces and identify the resulting boundaries. In Figure 4, adding the handle between faces Fi and F2 causes the embedding to become noncellular, as the resulting region is an annulus. However, once we start adding edges between the two boundary components of the annulus, the embedding becomes cellular again.
Construction 3.8. Let Fi = [ui,u2,..., ui] and F2 = [vi,v2,..., vj ] be two faces. Inserting the edge (ui, vi) in the following way
U\. ... ui u2 ...	ui. ... ui vi u2 ...
vi. ... vj v2 ...	vi. ... vj ui v2 ...
as in Figure 4 increases the genus by 1 and induces the (i + j + 2)-sidedface
[ui,u2, ...,ui, ui, vi, v2,... ,vj ,vi].
Figure 4: Adding a handle between two faces, then adding an edge to transform the annulus into a cell. Note that the order of vertices of one of the faces becomes reversed as we traverse one of the (oriented) boundaries the annulus.
The most elementary operation one can do is to simply add one edge to create a genus embedding:
316
Ars Math. Contemp. 18 (2020) 187-210
Proposition 3.9. If there exists a triangular embedding ^: Kn — K2 ^ Sg, then there exists a genus embedding of Kn in the surface Sg+1.
The forthcoming additional adjacency solutions are to be applied on triangular embed-dings of graphs of the form Kn — Ke, which is the graph formed by taking the complete graph Kn and deleting all the pairwise adjacencies between I vertices. We label the vertices missing adjacencies with bold letters a, b, c,..., h. The remaining vertices will be assigned numbers and are represented here as unadorned letters (u, v,p,...). We apply the traditional method of adding handles to supply all the missing edges—in Section 3.1, we give an alternative viewpoint that aims to demystify the specific choices of added edges.
Lemma 3.10. If there exists a triangular embedding of Kn — K5 with numbered vertices u and v whose rotations are of the form
and
u. ... a pi b p2 c p3 d p4 e ...
v ... Pff(l) Pa(2) . . . Pa(3) Pa(4) . . . , where a : {1,..., 4} ^ {1,..., 4} is some permutation, then there exist (n, 10)- and (n, 4)-triangulations and a triangle-tight embedding of Kn.
Proof. The initial embedding is an (n, 10)-triangulation. First, delete the edges (u,p1), (u, b), (u,p2 ) in exchange for (a, b), (a, c), (b, c) and apply edge flips on (u,p3) and (u,p4) to obtain (c, d) and (d, e), as in Figure 5(a). If we merge the faces [a, c, b] and [u, e, d] with a handle, we can recover the deleted edge (u, b) and add in the remaining edges between lettered vertices following Figure 5(b). The missing edges (u,p1),..., (u,p4) in this (n, 4)-triangulation can be reinserted with one handle using Proposition 3.6, setting pCT(i) = qi, to get a triangle-tight embedding of Kn.	□
c
P^r^P 3
P2 c P3
P4 Pi
II ^^oa
(a)
(b)
Figure 5: Various edge flips are applied in the neighborhood of vertex u (a) so that one handle suffices for connecting all the lettered vertices.
Lemma 3.11 (Guy and Ringel [5]). If there exists a triangular embedding of Kn — K6 with a numbered vertex u whose rotation is of the form
a pi b
C P2 d
e P3 f
then there exist (n, 15)-, (n, 9)-, and (n, 3)-triangulations and a triangle-tight embedding of Kn.
C
b
T. Sun: Simultaneous current graph constructions ...
317
Proof. We first modify the embedding near vertex u using edge flips to gain the edges (a,b), (c, d), and (e,f), as in Figure 6(a). If we apply Construction 3.1 to vertex u, we obtain a 9-sided face incident with all six vertices a, b, ... , f. In Figure 6(b) and (c), we give one way to insert the twelve missing edges between these lettered vertices with the help of a handle. The embeddings before and after adding the handle are (n, 9)- and (n, 3)-triangulations, respectively.
(a)
(b)
(c)
Figure 6: Three pairs of lettered vertices are connected with some edge flips (a), after which a handle adds some of the missing adjacencies (b). The remaining edges between lettered vertices are added using another handle merging faces I and II (c).
b
v
a
d
v
c
a
The missing edges (u,p1), (u,p2), (u,p3) can be added back using Corollary 3.7, yielding a triangle-tight embedding of Kn.	□
Lemma 3.12. If there exists a triangular embedding of Kn — K8 with numbered vertices u and v whose rotations are of the form
u. ... a pi b ... c p2 d ... e p3 f ... g p4 h ...
and
v. ... Pa( 1) Pa( 2) ... Pa( 3) Pa( 4) ...,
where a : {1,..., 4} —^ {1,..., 4} is some permutation, then there exist (n, 28)-, (n, 22)-, (n, 16)-, (n, 10)-, and (n, 4)-triangulations and a triangle-tight embedding of Kn.
Proof. The first four handles of our additional adjacency approach is the same as that of Ringel and Youngs' solution for Case 2-CG [19] (also see Ringel [16, §7.5]), with different
318
Ars Math. Contemp. 18 (2020) 187-210
vertex names. We perform an edge flip on each edge (u,pi) for i = 1,..., 4, gaining the edges (a, b), (c, d), (e, f), and (g, h). Now, the rotation at vertex u is of the form
u. ... a b ... c d ... e f ... g h ...
These edge flips are depicted in Figure 7. Applying Construction 3.2 to this resulting rotation yields two nontriangular faces
[h,g,v,d, c,v] and f, e,v, b,a,v].
Figure 7: Initial edge flips to join some of the vortex letters.
In these faces, we induce two quadrilateral faces by adding the edges (d, g), (c, h), (b, e), and (a,f ), as in Figure 8(a). Three more handles are used to add all the remaining edges between lettered vertices a,..., h as shown in Figure 8(bc). At this point, the embedding is of the graph Kn - K1,4 and is still triangular, so we add back the deleted edges (u,pi) with one handle using Proposition 3.6 to obtain a triangle-tight embedding of Kn.
The embeddings after adding the second through fourth handles are all triangular and hence are minimum triangulations. After adding only the first handle, the two quadrilateral faces in Figure 8(a) can be triangulated arbitrarily to form an (n, 22)-triangulation. □
We note some recurring themes in these additional adjacency solutions, which one could view as another form of unification between Cases. The "chord" edges and subsequent handle for connecting five vortices in Lemma 3.10 reappear in Lemma 3.11. Proposition 3.6 is invoked in both Lemma 3.10 and 3.12. As mentioned earlier, most of the construction in Lemma 3.12 was applied to Case 2-CG by Ringel and Youngs [19].
3.1 Recasting handle operations
Additional adjacency solutions are traditionally presented as a sequence of handles, which has the benefit of constructing some of the requisite minimum triangulations. However, when several handles are involved, it is not immediately apparent how such a construction was derived—Ringel [16] described the solution for Case 2-CG, which is largely identical to the one we used in Lemma 3.12, as "adventurous" and "much easier to understand than to discover." We can instead interpret parts of these additional adjacency solutions as surgical operations that glue together existing embeddings, akin to the diamond sum operation of
T. Sun: Simultaneous current graph constructions ...
319
b
h
(a)
d
c
d
h
b
d
c
e
(b)
(c)
Figure 8: After connecting some of the lettered vertices with a handle (a), another handle can be introduced in between the faces I and II (b). Using faces generated from this handle (III and IV, V and VI), we can add all the remaining edges using two additional handles (c).
Bouchet [1] or the inductive constructions found in Ringel [16, §10]. In our case, we make use of the embedding of K6 in Si formed by deleting a vertex from the triangular embedding of K7, and a genus embedding of K8 in S2 where the two quadrilateral faces are incident with disjoint sets of vertices. An example of the latter embedding appears in Ringel [16, p. 79] and is reproduced in Appendix C.
Recall that in Lemma 3.12, the second, third, and fourth handles add all the remaining missing edges between lettered vertices, where all of the activity takes place inside of the two quadrilateral faces formed from the first handle. Let ^: G ^ Sg be the embedding of the graph after the first handle in Lemma 3.12. Combining the next three handles into one step is equivalent to the following procedure, which is sketched in Figure 9:
• Excise the interiors of the quadrilateral faces of ^ and the aforementioned embedding
• Identify the two embedded surfaces at their boundaries so that the two disjoint sets of four vertices become identified and the resulting surface is orientable.
Hence the three handles are equivalent to a construction of a genus embedding of K8. We may also apply the same idea to reinterpret the constructions in Lemma 3.10 and 3.11 using the embedding of K6. If, for example, we remove the edges (b, c), (b, d), and (c, e) from Figure 6, we have the hexagonal face [a, d, c, f, e, b]. The goal of the last handle of the additional adjacency step in Lemma 3.11 is to add all the remaining edges between the lettered vertices, which we may accomplish by attaching the embedding of K6 along this hexagonal face, as shown in Figure 10.
Kg ^ S2.
320
Ars Math. Contemp. 18 (2020) 187-210
G * Kg ^ Sg+3
Figure 9: Adding adjacencies between eight vertices with an embedding of K8. Note that the genus increases by 3 since two boundary components are identified.
G * K6 ^ Sg+1
Figure 10: An alternative way of adding the edges between six vertices using one handle.
T. Sun: Simultaneous current graph constructions ...
321
4 Index 3 current graphs
We assume familiarity with current graphs, especially §9 of Ringel [16]. An index k current graph is a triple (D, a), where D is a directed graph, ^: D ^ S is a cellular k-face embedding of D in an orientable surface S and a: E(D) ^ r is a labeling of each arc of D with an element of a group r. These arc labels are called currents, and r is referred to as the current group. In this paper, we only consider index 3 current graphs that are labeled with elements from cyclic current groups r = Z3m for some integer m. Its three face boundary walks, which we call circuits, are labeled [0], [1], and [2].
The excess of a vertex is the sum of the incoming currents minus the sum of the outgoing currents, and we say a vertex satisfies Kirchhoff's current law (KCL) if its excess is 0. Vertices of degree 3 which do not satisfy KCL are called vortices, which are each labeled with a lowercase letter. The log of a circuit records the currents encountered along the walk in the following manner: if we traverse arc e along its orientation, we write down a(e); otherwise, we write down —a(e); if we encounter a vortex, we record its label. If the order 2 element y G Z3m is the current of an arc incident with a vertex of degree 1, it appears twice consecutively in the log of the incident circuit. We discard one of those instances so that the embedded graph is simple. Our drawings of current graphs which have such arcs follow the convention where the degree 1 vertex is omitted.
All of our index 3 current graphs with current groups Z3m satisfy the following additional "construction principles", which are effectively the same as those in Ringel [16, §9.1]:
(E1) Each vertex is of degree 3 or 1.
(E2) The embedding has three circuits labeled [0], [1], [2].
(E3) The log of each circuit consists of each nonzero element of Z3m exactly once and any number of vortex letters.
(E4) KCL is satisfied at every vertex of degree 3, except vortices, which are labeled with letters.
(E5) Every vortex is incident with all three circuits and has an excess which generates the subgroup of Z3m consisting of the multiples of 3.
(E6) If circuit [a] traverses arc e along its orientation and circuit [b] traverses e in the opposite direction, then a(e) = b — a (mod k).
(E7) The current on every arc incident with a vertex of degree 1 is of order 2 or 3 in Z3m.
If all the construction principles are satisfied, the current graph generates a triangular embedding of the graph K3m + Kg, where G + H is the graph join operation, G is the edge-complement of G, and £ is the number of vortices. Each element of Z3m corresponds to a vertex in the complete graph K3m, and each of the vortices provides an additional vertex, which is adjacent to all elements of Z3m, but none of the other vortex vertices. It is more common to think of the resulting graph instead as K3m+g — Kg, which highlights the total number of vertices and the number of missing edges needed to form a complete graph. An example of an index 3 current graph is given in Figure 11. The logs of its circuits are:
[0].	1 a 8 5 9 4 13 12 14 b 7 10 6 11 2 3
[1].	14 2 6 4 13 9 11 5 12 7 10 3 8 b 1 a
[2].	1 13 9 11 2 6 4 10 3 8 5 12 7 a 14 b
322
Ars Math. Contemp. 18 (2020) 187-210
To generate the embedding from the logs of these circuits, for each element 7 G Z3m in the group, the rotation at vertex 7 is found by taking the log of circuit [7 mod k] and adding 7 to each of its non-letter elements. The rotations at the numbered vertices thus read:
0.	1	a	8	5	9	4	13	12	14	b	7	10	6	11	2	3
1.	0	3	7	5	14	10	12	6	13	8	11	4	9	b	2	a
2.	3	0	11	13	4	8	6	12	5	10	7	14	9	a	1	b
3.	4	a	11	8	12	7	1	0	2	b	10	13	9	14	5	6
4.	3	6	10	8	2	13	0	9	1	11	14	7	12	b	5	a
5.	6	3	14	1	7	11	9	0	8	13	10	2	12	a	4	b
6.	7	a	14	11	0	10	4	3	5	b	13	1	12	2	8	9
7.	6	9	13	11	5	1	3	12	4	14	2	10	0	b	8	a
8.	9	6	2	4	10	14	12	3	11	1	13	5	0	a	7	b
9.	10	a	2	14	3	13	7	6	8	b	1	4	0	5	11	12
10.	9	12	1	14	8	4	6	0	7	2	5	13	3	b	11	a
11.	12	9	5	7	13	2	0	6	14	4	1	8	3	a	10	b
12.	13	a	5	2	6	1	10	9	11	b	4	7	3	8	14	0
13.	12	0	4	2	11	7	9	3	10	5	8	1	6	b	14	a
14.	0	12	8	10	1	5	3	9	2	7	4	11	6	a	13	b
The rotation around each lettered vertex is "manufactured" so that the entire embedding is triangular and orientable. To facilitate this process, we make use of the following characterization of triangular embeddings:
Proposition 4.1 (e.g., Ringel [16, §2.3]). An embedding of a simple graph G is triangular if and only if for all vertices i, j, k, if the rotation at vertex i is of the form
i. ... j k ...,
then the rotation at vertex j is of the form
j. . . . k i . . .
From the partial rotation system we have built up so far, we can determine the rotations at the remaining vortex vertices:
a.	0 1 2 9 10 11 3 4 5 12 13 14 6 7 8
b.	0 14 13 6 5 4 12 11 10 3 2 1 9 8 7
T. Sun: Simultaneous current graph constructions ...
323
The final embedding is a triangular one of K17 - K2, which is a (17,1)-triangulation. It can be augmented into a genus embedding of K17 using Proposition 3.9.
The group we use for most of our constructions, including all infinite families, is Zi2S+3. By combining construction principles (E6) and (E7), we find that in order to have a degree 1 vertex using this group, it must be the case that s = 2 (mod 3). Thus, we only make use of degree 1 vertices and principle (E7) in a few constructions deferred to Appendix B.
The increased flexibility acquired from using index 3 current graphs is crucial. Since vortices have the same degree as other vertices, one can tweak the number of vortices while keeping the number of total vertices and edges fixed, i.e., one cannot rule out the existence of such current graphs using just divisibility conditions on the numbers of vertices and edges in the current graph. Furthermore, the conditions in Lemma 3.10, i.e., having all five vortices lined up nearly consecutively, is only possible for current graphs with index at least 3. For indices 1 and 2, such a configuration would violate a "global" KCL condition.
A sketch of the standard proof of Case 5-CG (see Ringel [ , §9.2] or Youngs [ ]) is given first, as we reuse significant parts of its structure for our current graphs. The case s = 1 was given earlier in Figure 11, and the higher order cases are given in Figures 12 and 13. The construction also works trivially for s = 0 as well.
1 a 13
16
10	19
22
4	25
1 b 13	16	10	19	7	22	4
Figure 12: A current graph for K29 - K2.
Z
25
27
7
1
A
B
B
A
1
Z12s+3
1 a 6s+1	6s+4	6s-2	6s+7	6s-5	6s+10
10	12s-5	7	12s-2	4	12s+1	1
Figure 13: The family of current graphs for K12s+5 - K2, for general s. The omitted current on a circular arc is the same as those on the horizontal arcs above and below it.
324
Ars Math. Contemp. 18 (2020) 187-210
The general shape of the family of current graphs is a long ladder whose "rungs" alternate between simple vertical arcs and so-called "globular rungs," where the two additional vertices have a pair of parallel edges between them. As we parse from left to right, the vertical arcs, except for the arc connecting the two vortices, alternate in direction and form an arithmetic sequence consisting of the nonzero multiples of 3 in Zi2s+3. The zigzag pattern induced on the horizontal arcs is essentially the canonical graceful labeling of a path graph on 4s+1 vertices (see, e.g., Goddyn et al. [ ] for more information on this connection), where the vertical arcs correspond to the edge labels on the path graph. The horizontal arcs come in pairs that share the same current and are oriented in opposite directions. The currents on these arcs exhaust all the elements of the form 3k+1 in Zi2s+3.
Infinite families of current graphs typically consist of
•	a fixed portion, which contains vortices and some salient currents for additional adjacency solutions. The underlying directed graph stays the same, while the currents may vary as a function of s, and
•	a varying portion, which subsumes all remaining currents not present in the fixed portion. The size of this ingredient varies as a function of s, and the currents are arranged in a straightforward pattern.
In the construction for Case 5, we might consider the vortices and its incident edge ends as the fixed portion, and the rest of the graph (see Figure 14) as the varying portion. The elegant solutions for Cases 3 and 5 of the Map Color Theorem were first described in Youngs [23], improving upon similar ideas of Ringel [ ] and Gustin [ ]. We consider this varying portion, which we call the Youngs ladder, to be the best possible choice for index 3 current graphs.
The approach of Youngs et al. [ , , 2 ] first finalizes the fixed portion and then solve auxiliary labeling problems for the varying portion. We tackle the problem in reverse, opting to massage the fixed portion around a preset varying portion, which we choose to be a contiguous subset of the Youngs ladder. Starting with the arc labeled 1 that runs between the two vortices, we successively peel off rungs of the Youngs ladder until we have enough material for our desired fixed portion.
6s+1 6s+4 6s-2 6s+7	12s-2	4	12s+1	1
Figure 14: The Youngs ladder is essentially the current graphs for Case 5 with two vertices deleted.
We expect this procedure to become more difficult as the number of vortices increases-not only do we need appropriate currents that feed into the vortices, but there becomes an imbalance between the currents which are not divisible by 3 and those which are. Each vortex will use three currents of the former type, leaving a surplus of those of the latter type. The gadget in Figure 15, which we call the double bubble, accounts for this effect. By tracing out the partial circuits and invoking construction principle (E6), we find that
T. Sun: Simultaneous current graph constructions ...
325
all six currents entering the highest and lowest vertices must be divisible by 3, while the four remaining arcs may be labeled with an element not divisible by 3 depending on which circuits touch this gadget. The double bubble and its generalization have appeared in other work regarding current graphs of index greater than 1, such as Korzhik and Voss [ ] and Pengelley and Jungerman [ ].
In all of our current graph constructions, we use the cyclic group Z12s+3 unless we specify otherwise. While we often simplify the labels by reversing the directions of some arcs, e.g. replacing a label like 12s + 1 with 2, the ends which connect to the Youngs ladder are kept unchanged, i.e., as a current which is congruent to 1 (mod 3).
Figure 15: The "double bubble" motif appears in all of our general constructions. 5 Handle subtraction for minimum triangulations
The forthcoming embeddings K12s+3+k - Kk and the embeddings en route to constructing a genus embedding of K12s+3+k already constitute minimum triangulations, namely
where h is a nonnegative integer less than the number of added handles. To construct minimum triangulations on the same number of vertices, but with more missing edges, we turn to the main idea of Jungerman and Ringel [ ]: we enforce a specific structure in the current graph that allows us to "subtract" handles. The fragment shown in Figure 16 is what we refer as an arithmetic 3-ladder. If the step size h in the arithmetic sequence is divisible by 3 (more generally, divisible by the index of the current graph), then it is possible to find triangular embeddings in smaller-genus surfaces in the following manner:
<


t+h g+t
t
r
r-g
r+h
Figure 16: An arithmetic 3-ladder and a circuit passing through it.
326
Ars Math. Contemp. 18 (2020) 187-210
Lemma 5.1 (Jungerman and Ringel [11]). Let (D, a) be an index 3 current graph with current group Z3m that satisfies all construction principles. Suppose further that it has an arithmetic 3-ladder with step size divisible by 3. If the derived embedding of the current graph has | V | vertices and |E| edges, then for each k = 0,..., m, there exists a triangular embedding of a graph with | V | vertices and |E | — 6k edges.
Proof. Following Figure 16, the rotation at vertices 0 and h are of the form
0. ... — t—h g—h r g —t g+h r+h .. . h. .. . —t g r+h g+h	.. .
Here we used the fact that h is divisible by 3. We may infer, by repeated application of Proposition 4.1, the following partial rotation system, for i = 0,1,..., m:
0. .	. . g	—t	g+h	r+h
g. .	. . r+h	h	—t	0
r+h. .	. . 0	g+h	h	g
h. .	. . —t	g	r+h	g+h
—t. .	. . g+h	0	g	h
g+h. .	. . h	r+h	0	—t
If we delete the middle two columns, the rotation system becomes
0. . . . g r+h . . . g. . . . r+h 0 . . . r+h. . . . 0 g . . .
h. ... —t g+h . .. —t. ... g+h h ... g+h. ... h —t ...
This new embedding has six fewer edges, and is still triangular by Proposition 4.1, hence it must be a triangular embedding on a surface with one fewer handle by Proposition 2.1.
More generally, we obtain other handles that can be subtracted in the same manner, using the additivity rule. That is, we can find another subtractible handle by adding a multiple of 3 to every element of (5.1). The six edges from each of m handles can be deleted simultaneously, as none of the handles share any faces.	□
One way to visualize this operation is to interpret it as the reverse of Construction 3.8, like in Figure 17. One can check that in all instances in this paper, the number of handles we can subtract in a given embedding is greater than the number needed to realize the minimum triangulation with the fewest number of edges, i.e., the (n, t)-triangulation where t « n — 6.
6 The current graph constructions 6.1 Comparison with existing literature
Our utilization of index 3 current graphs is rooted in Jungerman and Ringel's [11] solution for Case 5-MT as a straightforward modification of the current graphs used for Case 5-CG.
T. Sun: Simultaneous current graph constructions ...
327
triangles.
We make no improvement here, but use a variation of their construction as an example of the infinite families of current graphs we seek.
The standard approach to Case 6-CG is to use index 3 current graphs to first obtain a triangular embedding of K12s+6-K3. The general solution Ringel [16, §9.3] chose to present works for all s > 4, and for s = 2, a current graph that makes use of construction principle (E7) is shown. Jungerman and Ringel [11] solved the remaining minimum triangulations using two families of index 1 current graphs. For s = 1, the case of (18, 3)-triangulations is particularly difficult—Jungerman [ ] found a triangular embedding of K18 - K3 using computer search, and we believe that such an embedding cannot be constructed with index 3 or lower current graphs (see the discussion in Section 6.3 and Appendix A). In [21], the author starts with an (18,9)-triangulation due to Jungerman and Ringel [10] and produces a (18,3)-triangulation and a genus embedding of K18. The (18, 3)-triangulation is of the graph Ki8 - 3K.
Index 1 embeddings of K12s+8 - K5 were apparently known to Ringel and Youngs (see Ringel [16, p. 86]), though they were unable to extend these embeddings to genus embeddings of K12s+8. Instead, Jungerman and Ringel [11] used them for most of the minimum triangulations on 12s + 8 vertices, i.e., the (12s + 8,10 + 6h)-triangulations for nonnegative h. For the remaining (12s + 8,4)-triangulation case, they found two families of index 2 current graphs whose derived embeddings could be modified into an embedding of K12s+8 - (K U P3).
The best solution for Case 9-CG is a beautiful construction of Jungerman, but it does not construct minimum triangulations except for the exceptional surface S2. For the general case, a family of current graphs found by Guy and Ringel [5]2 produced minimum triangulations for all s > 5. Jungerman and Ringel [11] supplied the remaining cases via a variety of approaches, primarily using an inductive construction where some triangular embeddings are glued to one another.
The only previously known solution for the genus of K12s+11 for s > 1 is that of Ringel and Youngs [18] for s > 2 and the asymmetric embedding of Mayer [13] for s = 1. In the general case, Ringel and Youngs start with an embedding of K12s+11 - K5, where the missing edges are added using a highly tailored additional adjacency step. The same current graph yields minimum triangulations of type (12s + 11,10 + 6h) for h > 0, but the troublesome case of (12s + 11,4)-triangulations, like in Case 8-MT, was resolved via
2There are two errors in Figure 1 of [5]: the top left current should be "6s + 1" and the vertex between "x" and "z" should be a vortex labeled "w."
328
Ars Math. Contemp. 18 (2020) 187-210
two complicated families of index 2 current graphs.
It seems that nowhere in the literature, including in the original proof of the Map Color Theorem, is there a construction of a genus embedding of Kn derived from an (n, 4)-triangulation. Even though we outlined a natural approach in Proposition 3.6 for converting an (n, 4)-triangulation to a genus embedding of Kn, no prior such unification was known.
Our approach gives a unified construction for both the Map Color Theorem and the minimum triangulations problem for Cases 6, 8, 9, and 11. The infinite families of current graphs cover all s > 2 for Cases 6, 8, and 9, and s > 3 for Case 11. In all these solutions, we use families of index 3 current graphs whose varying portions are a part of the Youngs ladder. One attractive property of using index 3 current graphs is that we are able to give a solution that does not break into two parts depending on the parity of s, as was the case in Jungerman and Ringel's [ ] current graphs for Case 6-, 8-, and 11-MT. For Cases 9 and 11, we supply additional constructions for smaller values of s. Of particular interest is the case of n = 23, for which we give the first current graph construction for a genus embedding of K23.
We present the constructions in increasing difficulty of the additional adjacency solution. In particular, Case 9, which has six vortices, is ultimately simpler than Case 8 because of the additional constraint needed in Lemma 3.10.
6.2 Case 5
As a warmup, let us consider how to find minimum triangulations for Case 5. The original solution in Figure 13 does not have any arithmetic 3-ladders, but we can modify it by swapping two of the rungs in the Youngs ladder, namely the two with vertical arcs labeled 6 and 12s - 3, as in Figure 18. In this drawing and all forthcoming figures, we only describe the fixed portion of the family of current graphs—at the ellipses, we complete the picture by attaching the corresponding segment of the Youngs ladder, as mentioned earlier. Exactly where to truncate the Youngs ladder is determined by the currents at the ends of the fixed portion.
12s-2 4 12s+1 1 x 6s+1	6s+4	6s-2
Figure 18: A slight modification to the Youngs ladder that produces minimum triangulations.
The idea of pairing the rungs is crucial in Youngs' method [ ] for constructing index 3 current graphs. In their proof of minimum triangulations for Case 5, Jungerman and Ringel [ ] took this idea to the extreme and switched all pairs of rungs so that all of the globular rungs appeared on one side of the ladder, but as seen in our example, implementing all these exchanges is not necessary.
We note that to the left of the vortices in our drawing in Figure 18, the directions of the arcs are inverted from that of Figure 13. Most of our infinite families (except the alternate Case 6-CG construction in Appendix A) involve attaching a Youngs ladder with a "Mobius
T. Sun: Simultaneous current graph constructions ...
329
twist," i.e., the final current graph is a long ladder-like graph whose top-left and bottom-left ends become identified with the bottom-right and top-right ends, respectively.
6.3 Case 6
The family of current graphs in Figure 19 applies for all s > 2 and has an arithmetic 3-ladder, giving a simpler and more unified construction for Case 6-CG (after applying Proposition 3.4), in addition to providing a single family of current graphs, irrespective of parity, for Case 6-MT. The case s =1 is particularly pesky—in the original proof of the Map Color Theorem, the minimum genus embedding of K18 was found using purely ad hoc methods by Mayer [ ]. An exhaustive computer search suggests that there are no index 3 current graphs for generating triangular embeddings of K18 — K3. In Appendix A, we present another solution for Case 6-CG, s > 2, that almost achieves the 18-vertex case.
12s-2 a	1	1	6s+1 6s+4 6s-2 6s+7
Figure 19: A current graph for K12s+6 - K3 for s > 2.
6.4 Case 9
We improve on the construction of Guy and Ringel [ ] with the family of index 3 current graphs seen in Figure 20. These current graphs produce triangular embeddings of K12s+9 — K6 for all s > 2, and the vertical rungs labeled 3,6,9 form an arithmetic 3-ladder. The circuits [1] and [2] have the six vortices packed as close together as possible. In particular, the log of circuit [1] reads
[1]. ... a 4 b ... c 1 d ... e 12s+1 f ...,
so we may apply Lemma 3.11 with, e.g., u = 1, to obtain (12s + 9,9)- and (12s + 9,3)-triangulations and a genus embedding of K12s+9.
For the case s = 1, Appendix B contains an index 3 current graph with an arithmetic 3-ladder that yields a triangular embedding of K21 — K3. The remaining case s = 0 is the lone exception to Theorem 2.6. Huneke [ ] proved that no triangulation of the surface S2 has 9 vertices, so the embedding of K8 in S2 with its quadrilateral faces subdivided (see Appendix C) is a minimum triangulation on 10 vertices. Adding an edge between these two subdivision vertices with Construction 3.8 and subsequently contracting that edge results in a genus embedding of K9.
330
Ars Math. Contemp. 18 (2020) 187-210
12s-2	1 f 4 c 2 b 6s+1 6s+4 6s-2 6s+7
Figure 20: A current graph for K12s+9 - K6 for s > 2. Additional fragments of circuits besides the guidelines at the left and right ends indicate components used in the additional adjacency solution.
6.5 Case 8
The family of current graphs in Figure 21 yields triangular embeddings of K12s+8 - K5 and has an arithmetic 3-ladder. The logs of this current graph are of the form
[0]. ... 6s+1 12s ... 12s-3 6s-2 ...
[2]. ... a 6s+2 b 12s+1 c 6s-1 d 12s-2 e ...
These translate, by additivity, to the rotations
3. ... 6s+4 0 ... 12s 6s+1 ...
2. ... a 6s+4 b 0 c 6s+1 d 12s e ...
By applying Lemma 3.10 with u = 2, v = 3, (p1,p2,p3,p4) = (6s + 4,0, 6s + 1,12s), we can construct a (12s + 8,4)-triangulation and a genus embedding of K12s+8.
7	1	e	5	d 4 a 6s+1 6s+4 6s-2 6s+7
6s-2
Figure 21: A family of index 3 current graphs for K12s+8 - K5, s > 2.
Remark 6.1. Our additional adjacency solution makes use of some of the arcs forming the arithmetic 3-ladder. However, there is no conflict since handle subtraction and additional adjacency operations are not applied simultaneously.
T. Sun: Simultaneous current graph constructions ...
331
6.6 Case 11
For s > 3, we introduce the family of current graphs in Figure 22 that generate triangular embeddings of K12s+11 - K8. On the bottom right is an arithmetic 3-ladder with labels 9,12,15. By examining circuit [1], we obtain the rotations
1. ... a 6s+8 b ... c 5 d ... e 12s-1 f ... g 6s+2 h ... 12s+1. ... 6s+8 6s+2 ... 5 12s-1 ...
Applying Lemma 3.12 with u = 1, v = 12s+1, (p1,p2,p3,p4) = (6s+8,5,12s-1,6s+2) yields the remaining minimum triangulations and a genus embedding of K12s+11, s > 3.
12s-5	7	5	1
Figure 22: Index 3 current graphs for K12s+11 - K8, s > 3.
The special cases s = 1, 2 have current graphs found in Appendix B, and a rotation system for s = 0 is given in Appendix C.
7 Conclusion
We found index 3 constructions that produced simultaneous solutions to the genus of the complete graphs and to minimum triangulations of surfaces, for Cases 6, 8, 9, and 11:
•	Two constructions were presented for Case 6, s > 2 of the Map Color Theorem. Prior to the present paper, the only previously known current graph for s = 2 was not generalizable to higher values of s due to its use of construction principle (E7).
•	A significantly simpler solution was found for K12s+9 - K6 than that of Guy and Ringel [5] that also works for s = 2, 3.
•	We gave unified constructions for Cases 8 and 11. For the latter, they are the first known triangular embeddings of K12s+11 - K8 for s > 3, and the case s = 1 for Case 11-CG now has a solution using current graphs. The additional adjacency
332
Ars Math. Contemp. 18 (2020) 187-210
solution for Case 11 (Lemma 3.12) is more straightforward than the original construction by Ringel and Youngs [18], especially in light of the interpretation given in Section 3.1.
As mentioned earlier, index 3 current graphs allow for changing the number of vortices without violating divisibility conditions necessary for the existence of current graphs. We expect that for fixed k > 1 and sufficiently large s, there exist appropriate current graphs for triangular embeddings of K12s+3+k - Kk. The results of this paper extend the applicability of index 3 current graphs to roughly half of both of the Map Color Theorem and the minimum triangulations problem, and we believe that a complete solution for a sufficiently large number of vertices is possible by extending the results presented here.
We made use of the current group Z12s+3 in our infinite families of current graphs, reserving the group Z12s+6 for the special cases presented in the Appendix B. We were unable to find triangular embeddings of K12s+9 - K6 and K12s+11 - K8 for small values of s, so we resorted to a different approach for these cases. An open problem would be to find an analogue of the Youngs ladder for the latter group—one tricky aspect is incorporating the order 2 element 6s + 3 into such a pattern. A desirable application of such a method would be a unified construction for all s > 1 for Case 11. Our current graph for s = 1, the first known current graph construction for finding a genus embedding of K23, is a step towards that goal.
Some recent unifications were found by the author in the context of index 1 current graphs. Originally, these constructions were meant to improve Case 0-CG [22] and Case 1-CG [20], but these current graphs also have arithmetic 3-ladders and hence also constitute unified constructions that improve upon those found in Jungerman and Ringel [11]. At present, Case 2 is the least unified of the residues. Triangular embeddings of K12s+2 -K2 for all s > 1 were found by Jungerman [9], which by Construction 3.8 yields genus embeddings of K12s+2. The remaining minimum triangulations were found by an entirely different construction by Jungerman and Ringel [11]. It seems plausible that lifting to index 3 current graphs may help, as it did with K20 (see [20]) and K23.
ORCID iD
Timothy Sun © https://orcid.org/0000-0002-5994-8838 References
[1]	A. Bouchet, Orientable and nonorientable genus of the complete bipartite graph, J. Comb. Theory Ser. B 24 (1978), 24-33, doi:10.1016/0095-8956(78)90073-4.
[2]	L. Goddyn, R. B. Richter and J. Siran, Triangular embeddings of complete graphs from graceful labellings of paths, J. Comb. Theory Ser. B 97 (2007), 964-970, doi:10.1016/j.jctb.2007.02.009.
[3]	J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1987.
[4]	W. Gustin, Orientable embedding of Cayley graphs, Bull. Amer. Math. Soc. 69 (1963), 272275, doi:10.1090/s0002-9904-1963-10952-0.
[5]	R. K. Guy and G. Ringel, Triangular imbedding of Kn - K6, J. Comb. Theory Ser. B 21 (1976), 140-145, doi:10.1016/0095-8956(76)90054-x.
[6]	R. K. Guy and J. W. T. Youngs, A smooth and unified proof of cases 6, 5 and 3 of the Ringel-Youngs theorem, J. Comb. Theory Ser. B 15 (1973), 1-11, doi:10.1016/0095-8956(73)90026-9.
T. Sun: Simultaneous current graph constructions ...
333
[7]	J. P. Huneke, A minimum-vertex triangulation, J. Comb. Theory Ser. B 24 (1978), 258-266, doi:10.1016/0095- 8956(78)90043- 6.
[8]	M. Jungerman, Orientable triangular embeddings of K1s — K3 and K13 — K3, J. Comb. Theory Ser. B 16 (1974), 293-294, doi:10.1016/0095-8956(74)90076-8.
[9]	M. Jungerman, The genus of Kn — K2, J. Comb. Theory Ser. B 18 (1975), 53-58, doi:10.1016/ 0095-8956(75)90064-7.
[10]	M. Jungerman and G. Ringel, The genus of the n-octahedron: regular cases, J. Graph Theory 2 (1978), 69-75, doi:10.1002/jgt.3190020109.
[11]	M. Jungerman and G. Ringel, Minimal triangulations on orientable surfaces, Acta Math. 145 (1980), 121-154, doi:10.1007/bf02414187.
[12]	V. P. Korzhik and H.-J. Voss, Exponential families of non-isomorphic non-triangular orientable genus embeddings of complete graphs, J. Comb. Theory Ser. B 86 (2002), 186-211, doi:10. 1006/jctb.2002.2122.
[13]	J. Mayer, Le probleme des regions voisines sur les surfaces closes orientables, J. Comb. Theory 6 (1969), 177-195, doi:10.1016/s0021-9800(69)80118-3.
[14]	D. J. Pengelley and M. Jungerman, Index four orientable embeddings and case zero of the Heawood conjecture, J. Comb. Theory Ser. B 26 (1979), 131-144, doi:10.1016/0095-8956(79) 90051-0.
[15]	G. Ringel, Über das Problem der Nachbargebiete auf orientierbaren Flachen, Abh. Math. Sem. Univ. Hamburg 25 (1961), 105-127, doi:10.1007/bf02992781.
[16]	G. Ringel, Map Color Theorem, volume 209 of Die Grundlehren der mathematischen Wissenschaften, Springer-Verlag, New York-Heidelberg, 1974.
[17]	G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438-445, doi:10.1073/pnas.60.2.438.
[18]	G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem—case 11, J. Comb. Theory 7 (1969), 71-93, doi:10.1016/s0021-9800(69)80008-6.
[19]	G. Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem—case 2, J. Comb. Theory 7 (1969), 342-352, doi:10.1016/s0021-9800(69)80061-x.
[20]	T. Sun, Face distributions of embeddings of complete graphs, arXiv:1708.02092 [math.CO].
[21]	T. Sun, Jungerman ladders and index 2 constructions for genus embeddings of dense regular graphs, arXiv:1911.05214 [math.CO].
[22]	T. Sun, A simple construction for orientable triangular embeddings of the complete graphs on 12s vertices, Discrete Math. 342 (2019), 1147-1151, doi:10.1016/j.disc.2018.12.023.
[23]	J. W. T. Youngs, Solution of the Heawood map-coloring problem—Cases 3, 5, 6, and 9, J. Comb. Theory 8 (1970), 175-219, doi:10.1016/s0021-9800(70)80075-8.
334
Ars Math. Contemp. 18 (2020) 187-210
Appendix A An alternate family of current graphs for Case 6-CG
In Figure 23, we give another index 3 construction for triangular embeddings of Ki2s+6 -K3 using as much of the Youngs ladder as possible. The corresponding segment of the Youngs ladder has 4s - 5 rungs—if we had a family of current graphs where the varying portion was part of a Youngs ladder with one more rung, then an index 3 current graph would exist for s = 1 (with 0 rungs from the Youngs ladder). Thus, we argue that this construction, combined with our experimental results showing nonexistence for s = 1, maximizes the length of the Youngs ladder fragment used. As a side note, this family of current graphs uses the same building blocks known to Ringel et al.
12s-2	4	2	1 b 6s-1 c 6s-2
Figure 23: Another construction for triangular embeddings of Ki2s+6 - K3.
Appendix B Small current graphs, Cases 9 and 11 B.1 Case 9
For s = 1 we use the special current graph in Figure 24. It is essentially one of the inductive constructions used by Jungerman and Ringel [11], with the additional observation that the current graph used has an arithmetic 3-ladder.
B.2 Case 11
For s = 1, 2, we first find a current graph with group Zi2s+6 that generates a triangular embedding of Ki2s+ii - K5. For s = 1, consider the index 3 current graph in Figure 25.
T. Sun: Simultaneous current graph constructions ...
335
The rotations at vertices 1 and 12 are of the form
1.	... a 3 b 5 c 9 d 8 e ... 12. ... 5 8 ... 3 9 ...,
so applying Lemma 3.10 with u = 1, v = 12, (pi,p2,p3,p4) = (3, 5, 9, 8) yields (23,10)-and (23,4)-triangulations, and a genus embedding of K23. For s = 2, the current graph in Figure 26 generates a triangular embedding of K35 - K5. Similar to the s = 1 case, we use the rotations
2.	... a 10 b 6 c 7 d 3 e ... 19. ... 7 10 ... 6 3 ...,
and Lemma 3.10 to find the (35,10)- and (35,4) triangulations, and a genus embedding of K35. The remaining minimum triangulations can be found using the arithmetic 3-ladder.
13_ 10	16 d 10 c 7
/13
4	1 e 13 b 16 0 1
Figure 25: An index 3 current graph for K23 - K5.
Z
18
An embedding is said to be nearly triangular if it has at most one nontriangular face. The following result relates nearly triangular embeddings to minimum triangulations:
Proposition B.1. Suppose there exists a triangle-tight embedding of Kn in a surface Sg with exactly one nontriangular face. If the boundary of the nontriangular face contains no repeated vertices, then there exists a minimum triangulation of Sg on n +1 vertices.
4
4
A
A
B
B
7
7
Proof. The bounds derived from Heawood numbers H(g) (Propositions 2.3 and 2.4) show that MT(g) > n +1 (as H(g) is not an integer). Subdividing the nontriangular face of the embedding with a new vertex and connecting it to all the vertices along the face yields the desired triangulation.	□
In particular, the aforementioned nonexistence result for (9, 3)-triangulations due to Huneke [ ] was used to show that K8 does not have a nearly triangular embedding in S2 [ ]. We use the nearly triangular genus embedding of K22 given in [20] to construct the remaining (23,16)-triangulation.
Finally, a unification of the 11-vertex case using an asymmetric embedding is given in Appendix C.
336
Ars Math. Contemp. 18 (2020) 187-210
Appendix C Some small embeddings
We collect a few special embeddings in this section. The first such embedding, found in Ringel [ , p. 79], is of K8 with two additional subdivision vertices:
0.	2	7	3	1	4	5	6	qo
2.	4	1	5	3	6	7	0	qo
4.	6	3	7	5	0	1	2	qo
6.	0	5	1	7	2	3	4	qo
1.	7	6	5	2	4	0	3	qi
3.	1	0	7	4	6	2	5	qi
5.	3	2	1	6	0	4	7	qi
7.	5	4	3	0	2	6	1	qi
qo.	6	4	2	0				
qi.	1	3	5	7				
This embedding was used in several ways: it is a minimum triangulation of S2, it is a genus embedding of K9 after amalgamating q0 and qi, and three of the handles of Lemma 3.12 can be thought of as gluing this embedding at two quadrilateral faces.
Known (11,4)-triangulations and genus embeddings of K11 do not follow naturally from current graph constructions. To lessen the load of having to verify these special
T. Sun: Simultaneous current graph constructions ...
337
embeddings, we give a triangular embedding of Kn — C4:
0.	1	10	8	4	2	9	7	5	3	6
1.	0	6	4	8	5	9	3	7	2	10
to	0	4	10	1	7	6	5	8	3	9
3.	0	5	10	4	7	1	9	2	8	6
4.	0	8	1	6	9	5	7	3	10	2
5.	0	7	4	9	1	8	2	6	10	3
6.	0	3	8	10	5	2	7	9	4	1
7.	0	9	6	2	1	3	4	5		
8.	0	10	6	3	2	5	1	4		
9.	0	2	3	1	5	4	6	7		
10.	0	1	2	4	3	5	6	8		
The missing edges are (7,8), (8,9), (9,10), and (10, 7), which can be added with one handle using Construction 3.8 as in Figure 27. Note that this construction does not really make use of any specific structure in the embedding, as we can always find a face incident with a given edge. We thus formulate this additional adjacency approach more generally:
Proposition C.1. If there exists a triangular embedding of Kn — C4, then there exists a triangle-tight embedding of Kn.
10
10
8
9
8
7
0
6
Figure 27: A generic method for adding a C4 with one handle, applied to the triangular embedding of Kn - C4.