AAAbhijin Adiga

Abhijin Adiga

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Abhijin Adiga has a total of 5 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Cubicity, Degeneracy, and Crossing Number

    by Abhijin Adiga, L. Sunil Chandran, Rogers Mathew

    A $k$-box $B=(R_1,...,R_k)$, where each $R_i$ is a closed interval on the real line, is defined to be the Cartesian product $R_1\times R_2\times ...\times R_k$. If each $R_i$ is a unit length interval, we call $B$ a $k$-cube. Boxicity of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-boxes. Similarly, the cubicity of $G$, denoted as $\cubi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph $G$ with maximum degree $\Delta$, $\cubi(G)\leq \lceil 4(\Delta +1)\log n\rceil$. In this paper, we show that, for a $k$-degenerate graph $G$, $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since $k$ is at most $\Delta$ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in $O(n^2k)$ time to output a $8k(\lceil 2.42 \log n\rceil + 1)$ dimensional cube representation for $G$. An important consequence of the above result is that if the crossing number of a graph $G$ is $t$, then $\boxi(G)$ is $O(t^{1/4}{\lceil\log t\rceil}^{3/4})$ . This bound is tight up to a factor of $O((\log t)^{1/4})$. We also show that, if $G$ has $n$ vertices, then $\cubi(G)$ is $O(\log n + t^{1/4}\log t)$. Using our bound for the cubicity of $k$-degenerate graphs we show that cubicity of almost all graphs in $\mathcal{G}(n,m)$ model is $O(d_{av}\log n)$, where $d_{av}$ denotes the average degree of the graph under consideration.

  • Open Access

    A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

    by Abhijin Adiga, Jasine Babu, L. Sunil Chandran

    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^\epsilon$-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+\frac{1}{k})$-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where $k \ge 1$ 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+kn^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.

  • Cubicity of interval graphs and the claw number

    by Abhijin Adiga, L. Sunil Chandran


  • Open Access

    The Hardness of Approximating the Threshold Dimension, Boxicity and Cubicity of a Graph

    by Abhijin Adiga, Diptendu Bhowmick, L. Sunil Chandran

    A $k$-dimensional box is the Cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line. The {\it boxicity} of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of a collection of $k$-dimensional boxes. A unit cube in $k$-dimensional space or a $k$-cube is defined as the Cartesian product $R_1 \times R_2 \times ... \times R_k$ where each $R_i$ is a closed interval on the real line of the form $[a_i,a_i + 1]$. The {\it cubicity} of $G$, denoted as $\cub(G)$, is the minimum integer $k$ such that $G$ can be represented as the intersection graph of a collection of $k$-cubes. The {\it threshold dimension} of a graph $G(V,E)$ is the smallest integer $k$ such that $E$ can be covered by $k$ threshold spanning subgraphs of $G$. In this paper we will show that there exists no polynomial-time algorithm to approximate the threshold dimension of a graph on $n$ vertices with a factor of $O(n^{0.5-\epsilon})$ for any $\epsilon >0$, unless $NP=ZPP$. From this result we will show that there exists no polynomial-time algorithm to approximate the boxicity and the cubicity of a graph on $n$ vertices with factor $O(n^{0.5-\epsilon})$ for any $ \epsilon >0$, unless $NP=ZPP$. In fact all these hardness results hold even for a highly structured class of graphs namely the split graphs. We will also show that it is NP-complete to determine if a given split graph has boxicity at most 3.

  • Open Access

    Boxicity and Poset Dimension

    by Abhijin Adiga, Diptendu Bhowmick, L. Sunil Chandran

    Let $G$ be a simple, undirected, finite graph with vertex set $V(G)$ and edge set $E(G)$. A $k$-dimensional box is a Cartesian product of closed intervals $[a_1,b_1]\times [a_2,b_2]\times...\times [a_k,b_k]$. The {\it boxicity} of $G$, $\boxi(G)$ is the minimum integer $k$ such that $G$ can be represented as the intersection graph of $k$-dimensional boxes, i.e. each vertex is mapped to a $k$-dimensional box and two vertices are adjacent in $G$ if and only if their corresponding boxes intersect. Let $\poset=(S,P)$ be a poset where $S$ is the ground set and $P$ is a reflexive, anti-symmetric and transitive binary relation on $S$. The dimension of $\poset$, $\dim(\poset)$ is the minimum integer $t$ such that $P$ can be expressed as the intersection of $t$ total orders. Let $G_\poset$ be the \emph{underlying comparability graph} of $\poset$, i.e. $S$ is the vertex set and two vertices are adjacent if and only if they are comparable in $\poset$. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset $\poset$, $\boxi(G_\poset)/(\chi(G_\poset)-1) \le \dim(\poset)\le 2\boxi(G_\poset)$, where $\chi(G_\poset)$ is the chromatic number of $G_\poset$ and $\chi(G_\poset)\ne1$. It immediately follows that if $\poset$ is a height-2 poset, then $\boxi(G_\poset)\le \dim(\poset)\le 2\boxi(G_\poset)$ since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph $G$ with a natural partial order associated with the \emph{extended double cover} of $G$, denoted as $G_c$: Note that $G_c$ is a bipartite graph with partite sets $A$ and $B$ which are copies of $V(G)$ such that corresponding to every $u\in V(G)$, there are two vertices $u_A\in A$ and $u_B\in B$ and $\{u_A,v_B\}$ is an edge in $G_c$ if and only if either $u=v$ or $u$ is adjacent to $v$ in $G$. Let $\poset_c$ be the natural height-2 poset associated with $G_c$ by making $A$ the set of minimal elements and $B$ the set of maximal elements. We show that $\frac{\boxi(G)}{2} \le \dim(\poset_c) \le 2\boxi(G)+4$. These results have some immediate and significant consequences. The upper bound $\dim(\poset)\le 2\boxi(G_\poset)$ allows us to derive hitherto unknown upper bounds for poset dimension such as $\dim(\poset)\le 2\tw(G_\poset)+4$, since boxicity of any graph is known to be at most its $\tw+2$. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree $\Delta$ is $O(\Delta\log^2\Delta)$ which is an improvement over the best known upper bound of $\Delta^2+2$. (2) There exist graphs with boxicity $\Omega(\Delta\log\Delta)$. This disproves a conjecture that the boxicity of a graph is $O(\Delta)$. (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on $n$ vertices with a factor of $O(n^{0.5-\epsilon})$ for any $\epsilon>0$, unless $NP=ZPP$.

  • Cubicity of threshold graphs

    by Abhijin Adiga


  • Open Access

    Cubicity of interval graphs and the claw number

    by Abhijin Adiga, L. Sunil Chandran

    Let $G(V,E)$ be a simple, undirected graph where $V$ is the set of vertices and $E$ is the set of edges. A $b$-dimensional cube is a Cartesian product $I_1\times I_2\times...\times I_b$, where each $I_i$ is a closed interval of unit length on the real line. The \emph{cubicity} of $G$, denoted by $\cub(G)$ is the minimum positive integer $b$ such that the vertices in $G$ can be mapped to axis parallel $b$-dimensional cubes in such a way that two vertices are adjacent in $G$ if and only if their assigned cubes intersect. Suppose $S(m)$ denotes a star graph on $m+1$ nodes. We define \emph{claw number} $\psi(G)$ of the graph to be the largest positive integer $m$ such that $S(m)$ is an induced subgraph of $G$. It can be easily shown that the cubicity of any graph is at least $\ceil{\log_2\psi(G)}$. In this paper, we show that, for an interval graph $G$ $\ceil{\log_2\psi(G)}\le\cub(G)\le\ceil{\log_2\psi(G)}+2$. Till now we are unable to find any interval graph with $\cub(G)>\ceil{\log_2\psi(G)}$. We also show that, for an interval graph $G$, $\cub(G)\le\ceil{\log_2\alpha}$, where $\alpha$ is the independence number of $G$. Therefore, in the special case of $\psi(G)=\alpha$, $\cub(G)$ is exactly $\ceil{\log_2\alpha}$. The concept of cubicity can be generalized by considering boxes instead of cubes. A $b$-dimensional box is a Cartesian product $I_1\times I_2\times...\times I_b$, where each $I_i$ is a closed interval on the real line. The \emph{boxicity} of a graph, denoted $ box(G)$, is the minimum $k$ such that $G$ is the intersection graph of $k$-dimensional boxes. It is clear that $ box(G)\le\cub(G)$. From the above result, it follows that for any graph $G$, $\cub(G)\le box(G)\ceil{\log_2\alpha}$.