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.