The Crossing Number of Pancake Graph $P_4$ is Six

Abstract

The crossing number of a graph $G$ is the smallest number of pairwise crossings of edges among all the drawings of $G$ in the plane. The pancake graph is an important network topological structure for interconnecting processors in parallel computers. In this paper, we prove the exact crossing number of the pancake graph $P_4$ is six.