  Let $H$, $T$ and $C_n$ be a graph, a tree and a cycle of order $n$,
respectively. Let $H^{(i)}$ be the complete join of $H$ and an empty graph on
$i$ vertices. Then the Cartesian product $H\Box T$ of $H$ and $T$ can be
obtained by applying zip product on $H^{(i)}$ and the graph produced by zip
product repeatedly. Let $\textrm{cr}_{\Sigma}(H)$ denote the crossing number of
$H$ in an arbitrary surface $\Sigma$. If $H$ satisfies certain connectivity
condition, then $\textrm{cr}_{\Sigma}(H\Box T)$ is not less than the sum of the
crossing numbers of its ``subgraphs". In this paper, we introduced a new
concept of generalized periodic graphs, which contains $H\Box C_n$. For a
generalized periodic graph $G$ and a function $f(t)$, where $t$ is the number
of subgraphs in a decomposition of $G$, we gave a necessary and sufficient
condition for $\textrm{cr}_{\Sigma}(G)\geq f(t)$. As an application, we
confirmed a conjecture of Lin et al. on the crossing number of the generalized
Petersen graph $P(4h+2,2h)$ in the plane. Based on the condition, algorithms
are constructed to compute lower bounds on the crossing number of generalized
periodic graphs in $\Sigma$. In special cases, it is possible to determine
lower bounds on an infinite family of generalized periodic graphs, by
determining a lower bound on the crossing number of a finite generalized
periodic graph.
