Search

The boxicity (respectively cubicity ) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k -dimensional boxes (respectively k -dimensional unit cubes) and is denoted by box ( G ) (respectively cub ( G ) ). It was shown by Adiga and Chandran (2010) that for any graph G , cub ( G ) ≤ box ( G ) ⌈ log 2 α ( G ) ⌉ , where α ( G ) is the maximum size of an independent set in G . In this note we show that cub ( G ) ≤ 2 ⌈ log 2 χ ( G ) ⌉ box ( G ) + χ ( G ) ⌈ log 2 α ( G ) ⌉ , where χ ( G ) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub ( G ) ≤ 2 ( box ( G ) + ⌈ log 2 α ( G ) ⌉ ) . Moreover, we show that for every positive integer k , there exist graphs with chromatic number k such that for every ϵ > 0 , the value given by our upper bound is at most ( 1 + ϵ ) times their cubicity. Thus, our upper bound is almost tight. [ABSTRACT FROM AUTHOR]

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in ℝk such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family Ƒ of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in Ƒ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Θ(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 29 log*dd. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least _d/2_. [ABSTRACT FROM AUTHOR]

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes touch just at their boundaries. [ABSTRACT FROM AUTHOR]

Abstract: The boxicity of a graph , denoted by , is the minimum integer such that is an intersection graph of axis-parallel -dimensional boxes in . In this paper we show that for a line graph of a multigraph, , where denotes the maximum degree of . Since is a line graph, , where denotes the chromatic number of , and therefore, . For the -dimensional hypercube , we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800]. The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once). [Copyright &y& Elsevier]

Abstract: The boxicity of a graph , denoted , is the least integer such that is the intersection graph of a family of -dimensional (axis-parallel) boxes. The cubicity, denoted , is the least such that is the intersection graph of a family of -dimensional unit cubes. An independent set of three vertices is an asteroidal triple if any two are joined by a path avoiding the neighbourhood of the third. A graph is asteroidal triple free (AT-free) if it has no asteroidal triple. The claw number is the number of edges in the largest star that is an induced subgraph of . For an AT-free graph with chromatic number and claw number , we show that and that this bound is sharp. We also show that . If is an AT-free graph having girth at least , then , and therefore . [Copyright &y& Elsevier]

Abstract: Let be a simple, undirected graph. A b-dimensional box is a Cartesian product , where each is a closed interval on the real line. When each interval has unit length we have a b-dimensional cube. The cubicity (respectively boxicity) of G, () is the minimum positive integer b such that the vertices in G can be mapped to axis parallel b-dimensional cubes (boxes) in such a way that two vertices are adjacent in G if and only if their assigned cubes (boxes) intersect. Suppose denotes a star graph on nodes. We define claw number to be the largest positive integer m such that is an induced subgraph of G. In this paper we show that for an interval graph . We also show that , where α is the independence number of G. From this we have, for any graph G, . [Copyright &y& Elsevier]

Abstract: A -dimensional box is the Cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as is the minimum integer such that is the intersection graph of a collection of -dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if is a Halin graph that is not isomorphic to , then . In fact, we prove the stronger result that if is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless is isomorphic to (in which case its boxicity is 1). [Copyright &y& Elsevier]

Abstract: An axis-parallel -dimensional box is a Cartesian product where each (for ) is a closed interval of the form on the real line. The boxicity of any graph , is the minimum positive integer such that G can be represented as the intersection graph of axis-parallel -dimensional boxes. A -dimensional cube is a Cartesian product , where each (for ) is a closed interval of the form on the real line. When the boxes are restricted to be axis-parallel cubes in -dimension, the minimum dimension required to represent the graph is called the cubicity of the graph (denoted by ). In this paper we prove that , where is the number of vertices in the graph. We also show that this upper bound is tight. Some immediate consequences of the above result are listed below: [1.] Planar graphs have cubicity at most . [2.] Outer planar graphs have cubicity at most . [3.] Any graph of treewidth has cubicity at most . Thus, chordal graphs have cubicity at most and circular arc graphs have cubicity at most , where is the clique number. The above upper bounds are tight, but for small constant factors. [Copyright &y& Elsevier]

Abstract: A -dimensional box is the cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as , is the minimum integer such that is the intersection graph of a collection of -dimensional boxes. A unit cube in -dimensional space or a -cube is defined as the cartesian product where each is a closed interval on the real line of the form . The cubicity of , denoted as , is the minimum such that is the intersection graph of a collection of -cubes. In this paper we show that and , where is the cardinality of a minimum vertex cover of and is the number of vertices of . We also show the tightness of these upper bounds. F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph , and , where is the number of vertices of , and these bounds are tight. We show that if is a bipartite graph then and this bound is tight. We also show that if is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , , then , where is the chromatic number of . [Copyright &y& Elsevier]

Abstract: For a graph , its cubicity is the minimum dimension such that is representable as the intersection graph of (axis-parallel) cubes in -dimensional space. (A -dimensional cube is a Cartesian product , where is a closed interval of the form on the real line.) Chandran et al. [L.S. Chandran, C. Mannino, G. Oriolo, On the cubicity of certain graphs, Information Processing Letters 94 (2005) 113–118] showed that for a -dimensional hypercube , . In this paper, we use the probabilistic method to show that . The parameter boxicity generalizes cubicity: the boxicity of a graph is defined as the minimum dimension such that is representable as the intersection graph of axis-parallel boxes in -dimensional space. Since for any graph , our result implies that . The problem of determining a non-trivial lower bound for is left open. [Copyright &y& Elsevier]

Abstract: An axis-parallel b-dimensional box is a Cartesian product where (for ) is a closed interval of the form on the real line. For a graph G, its boxicity is the minimum dimension b such that G is representable as the intersection graph of (axis-parallel) boxes in b-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research, etc. Though many authors have investigated this concept, not much is known about the boxicity of many well-known graph classes (except for a couple of cases) perhaps due to lack of effective approaches. Also, little is known about the structure imposed on a graph by its high boxicity. The concepts of tree decomposition and treewidth play a very important role in modern graph theory and have many applications to computer science. In this paper, we relate the seemingly unrelated concepts of treewidth and boxicity. Our main result is that, for any graph G, , where and denote the boxicity and treewidth of G, respectively. We also show that this upper bound is (almost) tight. Since treewidth and tree decompositions are extensively studied concepts, our result leads to various interesting consequences, like bounding the boxicity of many well-known graph classes, such as chordal graphs, circular arc graphs, AT-free graphs, co-comparability graphs, etc. For all these graph classes, no bounds on their boxicity were known previously. All our bounds are shown to be tight up to small constant factors. An algorithmic consequence of our result is a linear time algorithm to construct a box representation for graphs of bounded treewidth in a constant dimensional space. [Copyright &y& Elsevier]

Abstract: A d-dimensional box is a Cartesian product of d closed intervals on the real line. The boxicity of a graph is the minimum dimension d such that it is representable as the intersection graph of d-dimensional boxes. We give a short constructive proof that every graph with maximum degree D has boxicity at most . We also conjecture that the best upper bound is linear in D. [Copyright &y& Elsevier]

Abstract: We show that there exist series-parallel graphs with boxicity 3. [Copyright &y& Elsevier]

The boxicity of a graph G ( V , E ) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in R k . Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether the boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k = 2 or 3 . Computing these parameters is inapproximable within O ( n 1 − ϵ ) -factor, for any ϵ > 0 in polynomial time unless NP = ZPP , even for many simple graph classes. In this paper, we give a polynomial time κ ( n ) factor approximation algorithm for computing boxicity and a κ ( n ) ⌈ log log n ⌉ factor approximation algorithm for computing the cubicity, where κ ( n ) = 2 n log log n ∕ log n . These o ( n ) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question posed by Spinrad (2003) about polynomial time construction of o ( n ) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include O ( κ ( n ) ) factor approximation algorithms for computing the following parameters: the partial order dimension (poset dimension) of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, Ferrers dimension of digraphs and threshold dimension of split graphs and co-bipartite graphs. Each of these parameters is inapproximable within an O ( n 1 − ϵ ) -factor, for any ϵ > 0 in polynomial time unless NP = ZPP and the algorithms we derive seem to be the first o ( n ) factor approximation algorithms known for all these problems. We note that obtaining a o ( n ) factor approximation for poset dimension was also mentioned as an open problem by Felsner et al. (2017). In the second part of this paper, parameterized approximation algorithms for boxicity using various edit distance parameters are derived. We also present a parameterized approximation scheme for cubicity, using minimum vertex cover number as the parameter. [ABSTRACT FROM AUTHOR]

The boxicity (resp. cubicity) of a graph G ( V , E ) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R k . Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V , such that the intersection of their edge sets is E . The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O ( n 1 − ε ) -factor for any ε > 0 in polynomial time, unless N P = Z P P . For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n 1 − ε -factor approximation algorithm for computing boxicity in polynomial time, for any ε > 0 . In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs—intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Ω ( n ) . We give a ( 2 + 1 k ) -factor ( resp. ( 2 + ⌈ log n ⌉ k ) - factor ) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k ≥ 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O ( m n + n 2 ) in both these cases, and in O ( m n + k n 2 ) = O ( n 3 ) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. [ABSTRACT FROM AUTHOR]

Abstract: A -dimensional box is the Cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as , is the minimum integer such that can be represented as the intersection graph of a collection of -dimensional boxes. A unit cube in -dimensional space or a -cube is defined as the Cartesian product where each is a closed interval on the real line of the form . The cubicity of , denoted as , is the minimum integer such that can be represented as the intersection graph of a collection of -cubes. The threshold dimension of a graph is the smallest integer such that can be covered by threshold spanning subgraphs of . In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on vertices with a factor of for any unless . From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on vertices with factor for any unless . 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 -complete to determine whether a given split graph has boxicity at most 3. [ABSTRACT FROM AUTHOR]