Cubicity

In graph theory, cubicity is a graph invariant defined to be the smallest dimension such that a graph can be realized as an intersection graph of axis-parallel unit cubes in Euclidean space. Cubicity was introduced by Fred S. Roberts in 1969, along with a related invariant called boxicity that considers the smallest dimension needed to represent a graph as an intersection graph of axis-parallel rectangles in Euclidean space.

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.