Boxicity of circular arc graphs (Q659754): Difference between revisions

A \(k\)-dimensional box is a Cartesian product \(R_1\times\dots\times R_k\) where each \(R_i\) is a closed interval on the real line. The boxicity of a graph \(G\), denoted as \(\mathrm{box}(G)\), is the minimum integer \(k\) such that \(G\) can be represented as the intersection graph of a collection of \(k\)-dimensional boxes, i.e., there exists a one-to-one correspondence between the vertices of \(G\) and the boxes in the collection such that two vertices are adjacent if and only if their corresponding boxes have nonempty intersection. A circular arc graph is a graph that can be represented as the intersection graph of a collection of arcs on a circle. The authors prove for circular arc graphs \(G\) with \(n\) vertices: {\parindent=7mm \begin{itemize}\item[(1)]If \(G\) admits a circular arc (on a unit circle) representation with length of any arc less than \(\pi\frac{\alpha-1}{\alpha}\) for some integer \(\alpha \geq 2\), then \(\mathrm{box}(G)\leq \alpha\). It follows that if the maximum degree of \(G\) is less than \(\lfloor\frac{n(\alpha-1)}{2\alpha}\rfloor\) for some integer \(\alpha\geq 2\), then \(\mathrm{box}(G)\leq \alpha\). \item[(2)]If \(G\) admits a circular arc representation in which no arc is properly contained in another, i.e., \(G\) is a proper circular arc graph, and has maximum degree less than \(\lfloor\frac{n(\alpha-1)}{\alpha}\rfloor\) for some integer \(\alpha\geq 2\), then \(\mathrm{box}(G)\leq \alpha\). \item[(3)]If \(G\) admits a circular arc representation in which some point on the circle is crossed by at most \(r\) arcs, then \(\mathrm{box}(G)\leq r+1\) and this bound is tight. \item[(4)]If \(G\) admits a circular arc representation in which no family of at most \(3\) arcs covers the circle, then \(\mathrm{box}(G)\leq 3\), and if \(G\) admits a circular arc representation in which no family of at most \(4\) arcs covers the circle, then \(\mathrm{box}(G)\leq 2\). Both these bounds are tight. \end{itemize}}