A constant factor approximation algorithm for boxicity of circular arc graphs

In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs-intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Ω(n). We give a (2+1k)-factor (resp.(2+⌈logn⌉k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k≥1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn+n2) in both these cases, and in O(mn+kn2)=O(n3) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time.