Premium
The frame dimension and the complete overlap dimension of a graph
Author(s) -
Steif Jeffrey E.
Publication year - 1985
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190090210
Subject(s) - combinatorics , mathematics , intersection graph , graph , discrete mathematics , dimension (graph theory) , euclidean space , geometric graph theory , line graph , graph power
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.