An approximation algorithm for the boxicity of circular arc graphs

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 Rk . 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(n0.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.