Boxicity And Cubicity : A Study On Special Classes Of Graphs
Abstract
Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design.
An interval on the real line can be generalized to a k dimensional box or kbox. A kbox B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a kcube. Thus, an interval is a 1box and a unit length interval is a 1cube. A graph G has a kbox representation, if G is an intersection graph of a family of kboxes in Rk. Similarly, G has a kcube representation, if G is an intersection graph of a family of kcubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a kbox representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum
positive integer k such that G has a kcube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1.
The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NPcomplete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NPhard problems become polynomial time solvable.
Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work.
1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a kdegenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor.
2. For a kdegenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation.
3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ).
4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average degree.
5. Boxicity of a kleaf power is at most k 1. For every k, there exist kleaf powers whose boxicity is exactly k  1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity
6. Otachi et al. [8] conjectured that chordal bipartite graphs (CBGs) have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of CBGs that have unbounded boxicity. We first prove that the bipartite power of a tree (which is a CBG) is a CBG and then show that there exist trees whose bipartite powers have high boxicity. Later in Chapter ??, we prove a more generic result in bipartite powering. We prove that, for every k ≥ 3, the bipartite power of a bipartite, kchordal graph is bipartite and kchordal thus implying that CBGs are closed under bipartite powering.
7. Boxicity of a line graph with maximum degree Δ is O(Δ log2 log2 Δ). This is a log2 Δ
log log Δ
factor improvement over the best known upper bound for boxicity of any graph [1]. We also prove a nontrivial lower bound for the boxicity of a ddimensional hypercube.
Collections
Related items
Showing items related by title, author, creator and subject.

Rainbow Colouring and Some Dimensional Problems in Graph Theory
Rajendraprasad, Deepak (20180405)This thesis touches three diﬀerent topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices ... 
Rainbow Connection Number Of Graph Power And Graph Products
Arunselvan, R (20140909)The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. ... 
Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs
Babu, Jasine (20180508)This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These ...