2023/04/05 by Xiwu Yang, Xiaodong Cheng, Yang, Xiwu +3
Computer Science · Environmental Science · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Microplastics and Plastic Pollution
paper · pdf · doi:10.48550/arxiv.2304.02266
Let H, T and Cn 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 \textrmcrΣ(H) denote the crossing number of H in an arbitrary surface Σ. If H satisfies certain connectivity condition, then \textrmcrΣ(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 Cn. 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 \textrmcrΣ(G)≥ 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 Σ. 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.