Embedding Complete Bipartite Graphs with Cayley Maps

Our ability to replicate the optimal genera when embedding complete bipartite graphs onto orientable surfaces varied (See Table Below). Though with $K_{2,2}$ and $K_{3,3}$ we were able to obtain optimal genera 0 and 1, respectively, we found that it was impossible to obtain an optimal graph embedding for $K_{5,5}$ and $K_{7,7}$ using Cayley Maps. The smallest orientable surface $K_{5,5}$ can embed using this method is a six-holed torus, and $K_{7,7}$ can embed, at best, an
eight-holed torus. This is likely due to $K_{5,5}$ and $K_{7,7}$ being larger, and therefore more complex, than $K_{2,2}$ and $K_{3,3}$ . As shown in the table below we have yet to determine the minimum genus obtainable using a Cayley Map for $K_{11,11}$ . Because $K_{11,11}$ is much larger than the other complete bipartite graphs discussed, there are more possible face size combinations to rule out, and, as demonstrated in Theorem 7, doing so can be a lengthy process.

Though using Cayley Maps as a way to embed complete bipartite graphs may not produce the best genera, $K_{5,5}$ ‘s Cayley Map genus was only three higher than optimal, and $K_{7,7}$ ‘s was only one higher. Therefore, this method can still be useful if simplicity is a greater priority than genus optimality.

Graph Embeddings

Menu

Embedding Complete Bipartite Graphs with Cayley Maps