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

Keywords:

nonplanar graph; cubical graph; n-cube