×

Small nonplanar subgraphs of the cube. (English) Zbl 0623.05015

A graph G is said to be cubical if it is isomorphic to a subgraph of some n-cube. A cubical subdivision of a graph G with the minimum number of vertices is called a minimum subdivision of G. The authors prove that, to within isomorphism, there is a unique minimum subdivision of each of \(K_{3,3}\) and \(K_ 5\).
Reviewer: B.Alspach

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory