2011/01/01 by Abhijin Adiga, Diptendu Bhowmick, L. Sunil Chandran · 40 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Advanced Combinatorial Mathematics #Combinatorics #Mathematics #Cartesian product #Partially ordered set #Vertex (graph theory) #Discrete mathematics #Graph #Integer (computer science)
paper · doi:10.1137/100786290
published in SIAM Journal on Discrete Mathematics 25(4), 1687-1698 (Society for Industrial and Applied Mathematics)
openalex publication_date 2011/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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 [a1,b1]× [a2,b2]×⋯× [ak,bk]. 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 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 P, dim(P), is the minimum integer t such that P can be expressed as the intersection of t total orders. Let GP be the underlying comparability graph of P; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in 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 P, box(GP)/(χ(GP)-1) ≤ dim(P)≤ 2box(GP), where χ(GP) is the chromatic number of GP and χ(GP)≠1. It immediately follows that if P is a height-2 poset, then box(GP)≤ dim(P)≤ 2box(GP) 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 Gc: Note that Gc is a bipartite graph with partite sets A and B which are copies of V(G) such that, corresponding to every u∈ V(G), there are two vertices uA∈ A and uB∈ B and \uA,vB\ is an edge in Gc if and only if either u=v or u is adjacent to v in G. Let Pc be the natural height-2 poset associated with Gc by making A the set of minimal elements and B the set of maximal elements. We show that (box(G))/(2) ≤ dim(Pc) ≤ 2box(G)+4. These results have some immediate and significant consequences. The upper bound dim(P)≤ 2box(GP) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P)≤ 2 tree width (GP)+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 Δ is O(Δlog2Δ), which is an improvement over the best-known upper bound of Δ2+2. (2) There exist graphs with boxicity Ω(ΔlogΔ). This disproves a conjecture that the boxicity of a graph is O(Δ). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n0.5-ε) for any ε>0 unless NP=ZPP.