The frame dimension and the complete overlap dimension of a graph
Jeffrey E. Steif · Journal of Graph Theory · 1985
Abstract Roberts (F. S. Roberts, On the boxicity and cubicity of a graph. In Recent Progress in Combinatorics, W. T. Tutte, ed. Academic, New York (1969)), studied the intersection graphs of closed boxes (products of closed intervals) in Euclidean n‐space, and introduced the concept of the boxicity of a graph G, the smallest n such that G is the intersection graph of boxes in n‐space. In this paper, we study the intersection graphs of the frames or boundaries of such boxes. We study the frame dimension of a graph G—the smallest n such that G is the intersection graph of frames in n‐space. We also study the complete overlap dimension of a graph, a notion that is almost equivalent. The complete overlap dimension of a graph G is the smallest dimension in which G can be represented by boxes that intersect but are not completely contained in one another. We will prove that these dimensions are in almost all cases the same and that they both can become arbitrarily large. We shall also obtain a bound for these dimensions in terms of boxicity.