{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T09:31:55Z","timestamp":1778578315067,"version":"3.51.4"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,1,24]],"date-time":"2008-01-24T00:00:00Z","timestamp":1201132800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s00453-008-9163-5","type":"journal-article","created":{"date-parts":[[2008,1,23]],"date-time":"2008-01-23T12:52:43Z","timestamp":1201092763000},"page":"129-140","source":"Crossref","is-referenced-by-count":19,"title":["Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes"],"prefix":"10.1007","volume":"56","author":[{"given":"L. Sunil","family":"Chandran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathew C.","family":"Francis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naveen","family":"Sivadasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,24]]},"reference":[{"key":"9163_CR1","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. Theory Appl. 11, 209\u2013218 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9163_CR2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"Angluin, D., Valiant, L.G.: Fast probabilistic algorithms for Hamiltonian circuits and matchings. J.\u00a0Comput. Syst. Sci. 18, 155\u2013193 (1979)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9163_CR3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0012-365X(93)90354-V","volume":"114","author":"S. Bellantoni","year":"1993","unstructured":"Bellantoni, S., Hartman, I.B.-A., Przytycka, T., Whitesides, S.: Grid intersection graphs and boxicity. Discrete Math. 114, 41\u201349 (1993)","journal-title":"Discrete Math."},{"key":"9163_CR4","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1006\/jagm.2001.1188","volume":"41","author":"P. Berman","year":"2001","unstructured":"Berman, P., DasGupta, B., Muthukrishnan, S., Ramaswami, S.: Efficient approximation algorithms for tiling and packing problems with rectangles. J. Algorithms 41, 443\u2013470 (2001)","journal-title":"J. Algorithms"},{"key":"9163_CR5","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11, 1\u201321 (1993)","journal-title":"Acta Cybern."},{"key":"9163_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2 edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"key":"9163_CR7","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46, 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"issue":"5","key":"9163_CR8","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1016\/j.jctb.2006.12.004","volume":"97","author":"L.S. Chandran","year":"2007","unstructured":"Chandran, L.S., Sivadasan, N.: Boxicity and Treewidth. J. Comb. Theory Ser. B 97(5), 733\u2013744 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9163_CR9","author":"L.S. Chandran","year":"2007","unstructured":"Chandran, L.S., Francis, M.C., Sivadasan, N.: Boxicity and maximum degree. J. Comb. Theory Ser.\u00a0B (2007). doi: 10.1016\/j.jctb.2007.08.002","journal-title":"J. Comb. Theory Ser.\u00a0B"},{"key":"9163_CR10","unstructured":"Chandran, L.S., Francis, M.C., Sivadasan, N.: Geometric representation of graphs in low dimension using axis parallel boxes. Technical report available at http:\/\/arxiv.org\/pdf\/cs\/0605013"},{"key":"9163_CR11","unstructured":"Chang, Y.W., West, D.B.: Rectangle number for hyper cubes and complete multipartite graphs. In: 29th SE Conf. Comb., Graph Th. and Comp., Congr. Numer., vol. 132, pp. 19\u201328 (1998)"},{"key":"9163_CR12","unstructured":"Chang, Y.W., West, D.B.: Interval number and boxicity of digraphs. In: Proceedings of the 8th International Graph Theory Conf. (1998)"},{"key":"9163_CR13","unstructured":"Cozzens, M.B.: Higher and multidimensional analogues of interval graphs. Ph.D. thesis, Rutgers University, New Brunswick, NJ (1981)"},{"key":"9163_CR14","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T. Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34, 1302\u20131323 (2005)","journal-title":"SIAM J. Comput."},{"key":"9163_CR15","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0012-365X(79)90149-3","volume":"25","author":"R.B. Feinberg","year":"1979","unstructured":"Feinberg, R.B.: The circular dimension of a graph. Discrete Math. 25, 27\u201331 (1979)","journal-title":"Discrete Math."},{"key":"9163_CR16","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. Hastad","year":"1998","unstructured":"Hastad, J.: Clique is hard to approximate within n 1\u2212\u03b5 . Acta Math. 182, 105\u2013142 (1998)","journal-title":"Acta Math."},{"key":"9163_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. Lecture Notes in Computer Science, vol.\u00a0842. Springer, Berlin (1994)"},{"key":"9163_CR18","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J. Kratochvil","year":"1994","unstructured":"Kratochvil, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math. 52, 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"key":"9163_CR19","first-page":"301","volume-title":"Recent Progresses in Combinatorics","author":"F.S. Roberts","year":"1969","unstructured":"Roberts, F.S.: On the boxicity and Cubicity of a graph. In: Recent Progresses in Combinatorics, pp. 301\u2013310. Academic, New York (1969)"},{"key":"9163_CR20","first-page":"127","volume":"9","author":"B. Rosgen","year":"2007","unstructured":"Rosgen, B., Stewart, L.: Complexity results on graphs with few cliques. Discrete Math. Theor. Comput. Sci. 9, 127\u2013136 (2007)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"9163_CR21","unstructured":"Scheinerman, E.R.: Intersection classes and multiple intersection parameters. Ph.D. thesis, Princeton University (1984)"},{"key":"9163_CR22","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0012-365X(90)90290-X","volume":"29","author":"J.B. Shearer","year":"1980","unstructured":"Shearer, J.B.: A note on circular dimension. Discrete Math. 29, 103\u2013103 (1980)","journal-title":"Discrete Math."},{"key":"9163_CR23","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0095-8956(86)90061-4","volume":"40","author":"C. Thomassen","year":"1986","unstructured":"Thomassen, C.: Interval representations of planar graphs. J. Comb. Theory Ser. B 40, 9\u201320 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9163_CR24","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0012-365X(87)90247-0","volume":"64","author":"W.T. Trotter","year":"1987","unstructured":"Trotter, W.T., West, J.D.B.: Poset boxicity of graphs. Discrete Math. 64, 105\u2013107 (1987)","journal-title":"Discrete Math."},{"key":"9163_CR25","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. SIAM J. Algebraic Discrete Methods 3, 351\u2013358 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9163-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9163-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9163-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:01Z","timestamp":1559123101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9163-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,24]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["9163"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9163-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,24]]}}}