Boxicity

In the mathematical field of graph theory, the boxicity of a graph is a graph invariant defined to be the minimum dimension of Euclidean space required to represent the graph as an intersection graph of axis-parallel closed boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and these boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices.

Boxicity was introduced by Fred S. Roberts in 1969.

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.