A constant factor approximation algorithm for boxicity of circular arc graphs

DOI10.1007/978-3-642-22300-6_2MaRDI QIDQ5199227zbMATH OpenOpenAlexFDO

Authors Abhijin Adiga, Jasine Babu, L. Sunil Chandran

Publication date 12 August 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.1544

zbMATH Keywords

approximation algorithmboxicitycircular arc graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Abstract: Boxicity of a graph $G(V,E)$ is the minimum integer $k$ such that $G$ can be represented as the intersection graph of $k$-dimensional axis parallel rectangles in $mathbf{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$. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below $O(n^{0.5-epsilon})$-factor, for any $epsilon>0$ in polynomial time unless $NP=ZPP$. Till date, there is no well known graph class of unbounded boxicity for which even an $n^{e}psilon$-factor approximation algorithm for computing boxicity is known, for any $epsilon<1$. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a $(2+frac1k)$-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where $kge1$ is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is $O(mn+n^2)$ in both these cases and in $O(mn+k{n}^2)=O(n^3)$ time we also get their corresponding box representations, where $n$ is the number of vertices of the graph and $m$ is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

Recommendations

• A constant factor approximation algorithm for boxicity of circular arc graphs
• Boxicity of circular arc graphs
• Sublinear approximation algorithms for boxicity and related problems
• Polynomial time and parameterized approximation algorithms for boxicity

Cited in

(4)

• Lower bounds for boxicity
• Boxicity of circular arc graphs
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

This page was built for publication: A constant factor approximation algorithm for boxicity of circular arc graphs

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