View source for Cubicity

{{Short description|Graph invariant}}
[[File:A graph with cubicity 2.svg|thumb|upright=1.2|A cubicity 2 graph realized as the intersection graph of unit cubes, i.e. squares, in the plane.]]
In [[graph theory]], '''cubicity''' is a [[graph invariant]] defined to be the smallest dimension such that a [[Graph (discrete mathematics)|graph]] can be realized as an [[intersection graph]] of [[Unit cube|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 [[Hyperrectangle|rectangles]] in Euclidean space.<ref>Roberts, F. S. (1969). On the boxicity and cubicity of a graph. In W. T. Tutte (Ed.), ''Recent Progress in Combinatorics'' (pp. 301–310). San Diego, CA: Academic Press. ISBN 978-0-12-705150-5</ref>

== Definition ==
Let <math>G</math> be a graph. Then the ''cubicity'' of <math>G</math>, denoted by <math>\operatorname{cub} (G)</math>, is the smallest [[integer]] <math>n</math> such that <math>G</math> can be realized as an intersection graph of axis-parallel unit cubes in <math>n</math>-dimensional Euclidean space.<ref>{{Cite journal |last=Fishburn |first=Peter C |date=1983-12-01 |title=On the sphericity and cubicity of graphs |url=https://dx.doi.org/10.1016/0095-8956%2883%2990057-6 |journal=Journal of Combinatorial Theory, Series B |language=en |volume=35 |issue=3 |pages=309–318 |doi=10.1016/0095-8956(83)90057-6 |issn=0095-8956}}</ref>

The cubicity of a graph is closely related to the boxicity of a graph, denoted <math>\operatorname{box} (G)</math>. The definition of boxicity is essentially the same as cubicity, except in terms of using axis-parallel rectangles instead of cubes. Since a cube is a special case of a rectangle, the cubicity of a graph is always an upper bound for the boxicity of a graph. In the other direction, it can be shown that for any graph <math>G</math> on <math>m</math> vertices, the inequality <math>\operatorname{cub} (G) \leq \lceil \log_2 n \rceil \operatorname{box} (G)</math>, where <math>\lceil x \rceil</math> is the [[Floor and ceiling functions|ceiling function]], i.e., the smallest integer greater than or equal to <math>x</math>.<ref>{{Cite journal |last1=Sunil Chandran |first1=L. |last2=Ashik Mathew |first2=K. |date=2009-04-28 |title=An upper bound for Cubicity in terms of Boxicity |url=https://www.sciencedirect.com/science/article/pii/S0012365X08002240 |journal=Discrete Mathematics |language=en |volume=309 |issue=8 |pages=2571–2574 |doi=10.1016/j.disc.2008.04.011 |s2cid=7837544 |issn=0012-365X|arxiv=math/0605486 }}</ref>

== References ==
[[Category:Graph theory]]
<references />
[[Category:Discrete mathematics]]
[[Category:Geometric graph theory]]