Jasine Babu

A graph G is called an intersection graph of a family *F* of
geometric objects (say, rectangles), if each vertex of *G* can be
associated with an element of *F* in such a way that there is an
edge between two vertices of *G*, if and only if the corresponding
geometric objects intersect. Boxicity of a graph *G*(*V*,
*E*) is the minimum integer *k* such that *G* can
be represented as the intersection graph of axis parallel boxes in
R^{k} . Equivalently, it is the minimum number of interval
graphs on the vertex set *V* such that the intersection of their
edge sets is *E*. This parameter was introduced by Roberts in 1968
to study some problems in Ecology. It is known that boxicity cannot be
approximated even for graph classes like bipartite, co-bipartite and
split graphs below *O*(*n*^{0.5-ε})-factor,
for any ε>0 in polynomial time unless *NP* = *ZPP*.

I will present a work on the boxicity problem on Circular Arc (CA)
graphs - intersection graphs of arcs of a circle. We were able to get a
(2 + 1/*k*)-factor polynomial time approximation algorithm for
computing the boxicity of any CA graph along with a corresponding
box representation, where *k*≥1 is its boxicity. There is no
other well known graph class of unbounded boxicity for which even an
n^{ε}-factor approximation algorithm for computing
boxicity is known, for any ε<1.

Outline of the algorithm : For a subclass of CA graphs, called CA
co-bipartite graphs, boxicity can be computed in polynomial time, by
reducing it to the graph coloring problem of a related graph, which
happens to be a comparabilty graph. Given any CA graph *G*, we
construct a co-bipartite graph *G*' from it, which possesses some
nice adjacency struc ture, making it CA co-bipartite. Then, box(*G*)
is shown to be equal up to a constant factor of box(*G*'), which
is polynomial time computable.