21-25 August 2012
Portorož, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

Minimum Genus of Cartesian Products of Graphs

Presented by Michal KOTRBčIK
Type: Oral presentation

Content

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.

Place

Location: Portorož, Slovenia
Address: University of Primorska, Faculty of Tourism Studies, Obala 11a, SI-6320 Portorož - Portorose, Slovenia
Room: VP1

Primary authors

More