The minimum orientable genus of the repeated Cartesian product of graphs

Abstract

Determining the minimum genus of a graph is a fundamental optimisation problem in the study of network design and implementation as it gives a measure of non-planarity of graphs. In this paper, we are concerned with determining the smallest value of g such that a given graph G has an embedding on the orientable surface of genus g. In particular, we consider the Cartesian product of graphs since this is a well studied graph operation which is often used for modeling interconnection networks. The s-cube Qi(s) is obtained by taking the repeated Cartesian product of i complete bipartite graphs Ks,s. We determine the genus of the Cartesian product of the 2r-cube with the repeated Cartesian product of cycles and of the Cartesian product of the 2r-cube with the repeated Cartesian product of paths.