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.
[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 firstname.lastname@example.org and to email@example.com