A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs

Marco Caoduro, Will Evans, Tao Gaede

The boxicity of a graph $G$ is the minimum dimension $d$ that admits a representation of $G$ as the intersection graph of a family of axis-parallel boxes in ${\mathbb{R}}^d$. Computi…