The crossing number of pancake graph \(P_4\) is six. (English) Zbl 1424.05216
Summary: 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 pancake graph \(P_4\) is six.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68M10 | Network design and communication in computer systems |
