boxicity
Sign in to saveIn 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.
~5 min read
Article
7 sectionsContents
- Examples
- Relation to certain graph classes
- Algorithmic results
- Bounds
- Related graph invariants
- Notes
- References
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.