Boxicity and Interval-Orders: Petersen and the Complements of Line Graphs

Marco Caoduro, András Sebő

The boxicity of a graph is the smallest dimension $d$ allowing a representation of it as the intersection graph of a set of $d$-dimensional axis-parallel boxes. We present a simple…