Minimum Genus of Cartesian Products of Graphs
Presented by Michal KOTRBčIK
Type: Oral presentation
The minimum genus problem is a classical, but NP-complete problem in topological graph theory. Minimum genus of cartesian products is closely related to the minimum genus of a group, the minimum among genera of all Cayley graphs of the given group. For abelian groups, the most difficult case arises when the group contains a Z_3 factor in its canonical decomposition. In this talk we focus mainly on the genus of $G_n$, the cartesian product of $n$ triangles, which is the Cayley graph of the direct product of $n$ copies of $Z_3$. Characteristic features of the problem are a significant level of symmetry of the underlying graphs, very large problem space, and an absence of readily available methods. To determine the minimum genus of $Z_3$ we used both theoretical and computational approach. In this talk we focus on our practical experience with heuristics developed to obtain upper bounds, that is, low genus embeddings of $G_n$. In particular, we present currently the best upper bounds, which are quite irregular. This is a joint work with T. Pisanski.