Boxicity and Poset Dimension
Abhijin Adiga, Diptendu Bhowmick, L. Sunil Chandran · SIAM Journal on Discrete Mathematics · 2011
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\cdots\times [a_k,b_k]$. The boxicity of G, box$(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 $\mathcal{P}=(S,P)$ be a poset, where S is the ground set and P is a reflexive, antisymmetric and transitive binary relation on S. The dimension of $\mathcal{P}$, $\dim(\mathcal{P})$, is the minimum integer t such that P can be expressed as the intersection of t total orders. Let $G_{\mathcal{P}}$ be the underlying comparability graph of $\mathcal{P}$; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in $\mathcal{P}$. 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 $\mathcal{P}$, box$(G_{\mathcal{P}})/(\chi(G_{\mathcal{P}})-1) \le \dim(\mathcal{P})\le 2\mbox{box}(G_{\mathcal{P}})$, where $\chi(G_{\mathcal{P}})$ is the chromatic number of $G_{\mathcal{P}}$ and $\chi(G_{\mathcal{P}}) e1$. It immediately follows that if $\mathcal{P}$ is a height-2 poset, then box$(G_{\mathcal{P}})\le \dim(\mathcal{P})\le 2\mbox{box}(G_{\mathcal{P}})$ 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 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 $\mathcal{P}_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{\mbox{box}(G)}{2} \le \dim(\mathcal{P}_c) \le 2\mbox{box}(G)+4$. These results have some immediate and significant consequences. The upper bound $\dim(\mathcal{P})\le 2\mbox{box}(G_\mathcal{P})$ allows us to derive hitherto unknown upper bounds for poset dimension such as $\dim(\mathcal{P})\le 2\mbox{ tree width }(G_{\mathcal{P}})+4$, since boxicity of any graph is known to be at most its tree width $+\; 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$.