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