Characterization of the graphs with boxicity \(\leq 2\) (Q2277492)

The boxicity of a graph G is the least dimension d such that G is isomorphic to the incidence graph of a set of d-dimensional boxes. Interval graphs are graphs with boxicity 1, and are characterised as admitting an incidence matrix of vertices with maximal cliques C(G) such that in each column (corresponding to some vertex) all 1's are consecutive. In this paper an analogous characterization of graphs of boxicity 2 is derived. This is obtained by constructing a series of matrices by replacing certain elements of C(G) with *. G is then of boxicity 2 iff in each of these matrices all 1's are consecutive in each column, disregarding the *'s.