Nearly Triangular Imbeddings of Complete Graphs

An imbedding of a graph is *nearly triangular* if all but at most one region is triangular.

**Question:*** Do all complete graphs have nearly-triangular genus imbeddings?*

The Map Color Theorem [R] gives the genus of the complete graph. Triangular embeddings (and hence nearly triangular ones) exist for all *n* congruent to 0,3,4, or 7 (modulo 12). The constructions in [R] also cover several other congruence classes.

If the word ``genus'' is deleted, then an embedding with a single face is nearly triangular. These exist for *K(n)* whenever *n* is congruent to 2 or 3 (modulo 4). In the remaining congruence classes it is suspected that a nearly triangular embedding with exactly two faces can easily be constructed.

The question is related to the more general problem of finding non-isomorphic genus embeddings of the complete graph (see [LNW] and [GBGS]).

We can also ask similar questions for other graphs, such as complete multipartite graphs. I did not check, but believe, that the standard genus embeddings of complete bipartite graph are nearly quadrilateral.

**References:**

[GBGS] M.J. Grannell, C.P. Bonnington, T.S. Griggs, and J. Siran, Exponential families of non-isomorphic triangulations of complete graphs, preprint.

[LNW] S. Lawrencenko, S. Negami, and A.T. White, Three nonisomorphic triangulations of an orientable surface with the same complete graph, *Discrete Math.* **135** (1994)367-369.

[R] G. Ringel, Map Color Theorem, Springer-Verlag, New York, (1974).

Submitted by: David Craft

Send comments to *dan.archdeacon@uvm.edu* and to *craft@muskingum.edu*

August, 1995