2010/03/11 by Abhijin Adiga, Adiga, Abhijin, Diptendu Bhowmick +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.1003.2357
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 \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 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)/(χ(G_\poset)-1) ≤ dim(\poset)≤ 2\boxi(G_\poset), where χ(G_\poset) is the chromatic number of G_\poset and χ(G_\poset)≠1. It immediately follows that if \poset is a height-2 poset, then \boxi(G_\poset)≤ dim(\poset)≤ 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 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 \posetc 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 (\boxi(G))/(2) ≤ dim(\posetc) ≤ 2\boxi(G)+4. These results have some immediate and significant consequences. The upper bound dim(\poset)≤ 2\boxi(G_\poset) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(\poset)≤ 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 Δ 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.