A necessary and sufficient condition for lower bounds on crossing numbers of generalized periodic graphs in an arbitrary surface

Abstract

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\square T$ of $H$ and $T$ can be obtained by applying zip product on $H^{(i)}$ and the graph produced by zip product repeatedly. Let ${\text{cr}}_{\Sigma }(H)$ denote the crossing number of $H$ in an arbitrary surface $\Sigma$. If $H$ satisfies certain connectivity condition, then ${\text{cr}}_{\Sigma }(H\square 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\square 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 ${\text{cr}}_{\Sigma }(G)\ge 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.

26 pages, 20 figures