Boxicity of circular arc graphs

-dimensional boxes: that is two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. Let

G

be a circular arc graph with maximum degree

D e l t a

. We show that if

D e l t a < l f l o o r f r a c n (a l p h a - 1) 2 a l p h a f l o o r

,

a l p h a i n m a t h b b N

,

a l p h a g e q 2

then

b o x (G) l e q a l p h a

. We also demonstrate a graph with boxicity

> a l p h a

but with

D e l t a = n f r a c (a l p h a - 1) 2 a l p h a + f r a c n 2 a l p h a (a l p h a + 1) + (a l p h a + 2)

. So the result cannot be improved substantially when

a l p h a

is large. Let

r_{i n f}

be minimum number of arcs passing through any point on the circle with respect to some circular arc representation of

G

. We also show that for any circular arc graph

G

,

b o x (G) l e q r_{i n f} + 1

and this bound is tight. Given a family of arcs

F

on the circle, the circular cover number

L (F)

is the cardinality of the smallest subset

F^{'}

of

F

such that the arcs in

F^{'}

can cover the circle. Maximum circular cover number

L_{m a x} (G)

is defined as the maximum value of

L (F)

obtained over all possible family of arcs

F

that can represent

G

. We will show that if

G

is a circular arc graph with

L_{m a x} (G) > 4

then

b o x (G) l e q 3

.

Review text

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}}

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Boxicity of circular arc graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q659754)