{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T14:22:06Z","timestamp":1715955726426},"reference-count":32,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,3]],"date-time":"2006-10-03T00:00:00Z","timestamp":1159833600000},"content-version":"vor","delay-in-days":7794,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1985,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Roberts (F. S. Roberts, On the boxicity and cubicity of a graph. In <jats:italic>Recent Progress in Combinatorics<\/jats:italic>, W. T. Tutte, ed. Academic, New York (1969)), studied the intersection graphs of closed boxes (products of closed intervals) in Euclidean <jats:italic>n<\/jats:italic>\u2010space, and introduced the concept of the boxicity of a graph <jats:italic>G<\/jats:italic>, the smallest <jats:italic>n<\/jats:italic> such that <jats:italic>G<\/jats:italic> is the intersection graph of boxes in <jats:italic>n<\/jats:italic>\u2010space. In this paper, we study the intersection graphs of the frames or boundaries of such boxes. We study the frame dimension of a graph <jats:italic>G<\/jats:italic>\u2014the smallest <jats:italic>n<\/jats:italic> such that <jats:italic>G<\/jats:italic> is the intersection graph of frames in <jats:italic>n<\/jats:italic>\u2010space. We also study the complete overlap dimension of a graph, a notion that is almost equivalent. The complete overlap dimension of a graph <jats:italic>G<\/jats:italic> is the smallest dimension in which <jats:italic>G<\/jats:italic> 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.<\/jats:p>","DOI":"10.1002\/jgt.3190090210","type":"journal-article","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T07:17:26Z","timestamp":1180423046000},"page":"285-299","source":"Crossref","is-referenced-by-count":4,"title":["The frame dimension and the complete overlap dimension of a graph"],"prefix":"10.1002","volume":"9","author":[{"given":"Jeffrey E.","family":"Steif","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,3]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"K. S.BoothandG. S.Lueker Linear algorithms to recognize interval graphs and test for the consecutive ones property.Proc. 7th SCM Symp. Theory Computing(1975)255\u2013265.","DOI":"10.1145\/800116.803776"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"e_1_2_1_4_2","unstructured":"M.Buckingham Circle graphs. Courant computer science report No.21 New York University (1980)."},{"key":"e_1_2_1_5_2","unstructured":"M. B.Cozzens Higher\u2010dimensional and multi\u2010dimensional analogues of interval graphs. Ph.D. Thesis Department of Mathematics Rutgers University New Brunswick NJ (1981)."},{"key":"e_1_2_1_6_2","volume-title":"The NP\u2010completeness of the boxicity of a graph. Mimeographed","author":"Cozzens M. B.","year":"1982"},{"key":"e_1_2_1_7_2","volume-title":"k\u2010Suitable sets of arrangements and the boxicity of a graph. Mimeographed","author":"Cozzens M. B.","year":"1982"},{"key":"e_1_2_1_8_2","unstructured":"M. B.CozzensandF. S.Roberts Multi\u2010dimensional intersection graphs: Cubicity circular dimension overlap dimension. Mimeographed Department of Mathematics Rutgers University (1982)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90077-X"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/B978-0-12-417750-5.50011-7","volume-title":"Theory of Machines and Computations","author":"Even S.","year":"1971"},{"key":"e_1_2_1_11_2","first-page":"811","article-title":"Une caracterization des graphes de cordes","volume":"286","author":"Fournier J. C.","year":"1978","journal-title":"C.R. Acad. Sci. Paris."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1964-11160-5"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030305"},{"key":"e_1_2_1_14_2","series-title":"Proc. 11th Conf. on Information Sciences and Systems","first-page":"91","volume-title":"Some NP\u2010complete problems on graphs","author":"Gavril F.","year":"1977"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1964-055-5"},{"key":"e_1_2_1_16_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M.","year":"1980"},{"key":"e_1_2_1_17_2","unstructured":"T.Havel The combinatorial distance geometry approach to the calculation of molecular conformation. Ph.D. Thesis Group in Biophysics University of California Berkeley (1982)."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.2044-8317.1974.tb00534.x"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.2307\/2317880"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-51-1-45-64"},{"key":"e_1_2_1_21_2","first-page":"189","article-title":"Periodic extensive measurement","volume":"23","author":"Luce R. D.","year":"1971","journal-title":"Composite Math."},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.4064\/fm-33-1-303-307","article-title":"Sur deux proprietes des clases d'en sembles","volume":"33","author":"Marczewski E.","year":"1945","journal-title":"Fund. Math."},{"key":"e_1_2_1_23_2","first-page":"301","volume-title":"Recent Progress in Combinatorics","author":"Roberts F. S.","year":"1969"},{"key":"e_1_2_1_24_2","volume-title":"Discrete Mathematical Models","author":"Roberts F. S.","year":"1976"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970401"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1979.tb32824.x"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1002\/jcp.1040700403"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-16-1-386-389"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90137-7"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(74)80027-0"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0070412"},{"key":"e_1_2_1_32_2","unstructured":"A. C.Tucker An algorithm for circular\u2010arc graphs.SIAM J. Computing(1979)."},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90038-2"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190090210","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190090210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T05:28:57Z","timestamp":1697866137000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190090210"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,6]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,6]]}},"alternative-id":["10.1002\/jgt.3190090210"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190090210","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,6]]}}}