Intersection Graphs Of Boxes And Cubes

Abstract

A graph Gis said to be an intersection graph of sets from a family of sets if there exists a function ƒ : V(G)→ such that for u,v V(G), (u,v) E(G) ƒ (u) ƒ (v) ≠ . Interval graphs are thus the intersection graphs of closed intervals on the real line and unit interval graphs are the intersection graphs of unit length intervals on the real line. An interval on the real line can be generalized to a “kbox” in Rk.A kbox B =(R1,R2,...,Rk), where each Riis a closed interval on the real line, is defined to be the Cartesian product R1x R2x…x Rk. If each Ri is a unit length interval, we call B a k-cube. Thus, 1-boxes are just closed intervals on the real line whereas 2-boxes are axis-parallel rectangles in the plane. We study the intersection graphs of k-boxes and k-cubes. The parameter boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. Thus, interval graphs are the graphs with boxicity at most 1 and unit interval graphs are the graphs with cubicity at most 1. These parameters were introduced by F. S.Roberts in 1969. In some sense, the boxicity of a graph is a measure of how different a graph is from an interval graph and in a similar way, the cubicity is a measure of how different the graph is from a unit interval graph. We prove several upper bounds on the boxicity and cubicity of general as well as special classes of graphs in terms of various graph parameters such as the maximum degree, the number of vertices and the bandwidth. The following are some of the main results presented. 1. We show that for any graph G with maximum degree Δ , box(G)≤ Δ 22 . This result implies that bounded degree graphs have bounded boxicity no matter how large the graph might be. 2. It was shown in [18] that the boxicity of a graph on n vertices with maximum degree Δ is O(Δ ln n). But a similar bound does not hold for the average degree davof a graph. [18] gives graphs in which the boxicity is exponentially larger than davln n. We show that even though an O(davln n) upper bound for boxicity does not hold for all graphs, for almost all graphs, boxicity is O(davln n). 3. The ratio of the cubicity to boxicity of any graph shown in [15] when combined with the results on boxicity show that cub(G) is O(Δ ln 2 n) and O(2 ln n) for any graph G on n vertices and with maximum degree . By using a randomized construction, we prove the better upper bound cub(G) ≤ [4(Δ + 1) ln n.] 4. Two results relating the cubicity of a graph to its bandwidth b are presented. First, it is shown that cub(G) ≤ 12(Δ + 1)[ ln(2b)] + 1. Next, we derive the upper bound cub(G) ≤ b + 1. This bound is used to derive new upper bounds on the cubicity of special graph classes like circular arc graphs, cocomparability graphs and ATfree graphs in relation to the maximum degree. 5. The upper bound for cubicity in terms of the bandwidth gives an upper bound of Δ + 1 for the cubicity of interval graphs. This bound is improved to show that for any interval graph G with maximum degree , cub(G) ≤[ log2 Δ] + 4. 6. Scheinerman [54] proved that the boxicity of any outerplanar graph is at most 2. We present an independent proof for the same theorem. 7. Halin graphs are planar graphs formed by adding a cycle connecting the leaves of a tree none of whose vertices have degree 2. We prove that the boxicity of any Halin graph is equal to 2 unless it is a complete graph on 4 vertices, in which case its boxicity is 1.