{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,24]],"date-time":"2025-12-24T14:54:21Z","timestamp":1766588061722,"version":"3.38.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,10,19]],"date-time":"2011-10-19T00:00:00Z","timestamp":1318982400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2013,1]]},"DOI":"10.1007\/s00373-011-1099-x","type":"journal-article","created":{"date-parts":[[2011,10,18]],"date-time":"2011-10-18T08:41:09Z","timestamp":1318927269000},"page":"45-69","source":"Crossref","is-referenced-by-count":2,"title":["Cubicity and Bandwidth"],"prefix":"10.1007","volume":"29","author":[{"given":"L. Sunil","family":"Chandran","sequence":"first","affiliation":[]},{"given":"Mathew C.","family":"Francis","sequence":"additional","affiliation":[]},{"given":"Naveen","family":"Sivadasan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,19]]},"reference":[{"issue":"8","key":"1099_CR1","doi-asserted-by":"crossref","first-page":"2535","DOI":"10.1016\/j.disc.2008.05.004","volume":"309","author":"A. Adiga","year":"2009","unstructured":"Adiga A.: Cubicity of threshold graphs. Discrete Math. 309(8), 2535\u20132537 (2009)","journal-title":"Discrete Math."},{"key":"1099_CR2","doi-asserted-by":"crossref","unstructured":"Adiga, A., Chandran, L.S.: Cubicity of interval graphs and the claw number. European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009). Electron. Notes in Discrete Math. 34, 471\u2013475 (2009)","DOI":"10.1016\/j.endm.2009.07.078"},{"key":"1099_CR3","unstructured":"Afshani, P., Chan, T.M.: Approximation algorithms for maximum cliques in 3d unit-disk graphs. In: Proceedings of 17th Canadian Conference on Computational Geometry (CCCG), pp. 6\u20139 (2005)"},{"issue":"3\u20134","key":"1099_CR4","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. 11(3\u20134), 209\u2013218 (1998)","journal-title":"Comput. Geom."},{"issue":"2","key":"1099_CR5","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(2), 443\u2013470 (2001)","journal-title":"J. Algorithms"},{"issue":"8","key":"1099_CR6","doi-asserted-by":"crossref","first-page":"2488","DOI":"10.1016\/j.disc.2008.06.003","volume":"309","author":"L.S. Chandran","year":"2009","unstructured":"Chandran L.S., Das A., Shah C.D.: Cubicity, boxicity, and vertex cover. Discrete Math. 309(8), 2488\u20132496 (2009)","journal-title":"Discrete Math."},{"issue":"2","key":"1099_CR7","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s00453-008-9163-5","volume":"56","author":"L.S. Chandran","year":"2010","unstructured":"Chandran L.S., Francis M.C., Sivadasan N.: Geometric representation of graphs in low dimension using axis-parallel boxes. Algorithmica 56(2), 129\u2013140 (2010)","journal-title":"Algorithmica"},{"issue":"3","key":"1099_CR8","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.ipl.2005.01.001","volume":"94","author":"L.S. Chandran","year":"2005","unstructured":"Chandran L.S., Mannino C., Orialo G.: On the cubicity of certain graphs. Inform. Process. Lett. 94(3), 113\u2013118 (2005)","journal-title":"Inform. Process. Lett."},{"issue":"8","key":"1099_CR9","doi-asserted-by":"crossref","first-page":"2571","DOI":"10.1016\/j.disc.2008.04.011","volume":"309","author":"L.S. Chandran","year":"2009","unstructured":"Chandran L.S., Mathew K.A.: An upper bound for cubicity in terms of boxicity. Discrete Math. 309(8), 2571\u20132574 (2009)","journal-title":"Discrete Math."},{"issue":"6","key":"1099_CR10","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(6), 1302\u20131323 (2005)","journal-title":"SIAM J. Comput."},{"key":"1099_CR11","doi-asserted-by":"crossref","unstructured":"Feige, U.: Approximating the bandwidth via volume respecting embeddings. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 90\u201399. ACM Press (1998)","DOI":"10.1145\/276698.276716"},{"issue":"3","key":"1099_CR12","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0095-8956(83)90057-6","volume":"35","author":"P.C. Fishburn","year":"1983","unstructured":"Fishburn P.C.: On the sphericity and cubicity of graphs. J. Combin. Theory Ser. B 35(3), 309\u2013318 (1983)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"1099_CR13","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jpdc.1998.1424","volume":"49","author":"R. Heckmann","year":"1998","unstructured":"Heckmann R., Klasing R., Monien B., Unger W.: Optimal embedding of complete binary trees into lines and grids. J. Parallel Distrib. Comput. 49(1), 40\u201356 (1998)","journal-title":"J. Parallel Distrib. Comput."},{"key":"1099_CR14","doi-asserted-by":"crossref","unstructured":"Kloks, T., Kratsch, D., Borgne, Y.L., M\u00fcller, H.: Bandwidth of split and circular permutation graphs. In: Proceedings of the 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000), LNCS, vol. 1928. pp. 243\u2013254. Springer, Berlin (2000)","DOI":"10.1007\/3-540-40064-8_23"},{"issue":"1","key":"1099_CR15","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1006\/jagm.1998.0997","volume":"32","author":"T. Kloks","year":"1999","unstructured":"Kloks T., Kratsch D., M\u00fcller H.: Approximating the bandwidth of asteroidal triple-free graphs. J. Algorithms 32(1), 41\u201357 (1999)","journal-title":"J. Algorithms"},{"issue":"3","key":"1099_CR16","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1137\/0406032","volume":"6","author":"D. Kratsch","year":"1993","unstructured":"Kratsch D., Stewart L.: Domination on cocomparability graphs. SIAM J. Discrete Math. 6(3), 400\u2013417 (1993)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"1099_CR17","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1137\/S0895480199359624","volume":"15","author":"D. Kratsch","year":"2002","unstructured":"Kratsch D., Stewart L.: Approximating bandwidth by mixing layouts of interval graphs. SIAM J. Discrete Math. 15(4), 435\u2013449 (2002)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"1099_CR18","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0095-8956(86)90081-X","volume":"40","author":"H. Maehara","year":"1986","unstructured":"Maehara H.: Sphericity exceeds cubicity for almost all complete bipartite graphs. J. Combin. Theory Ser. B 40(2), 231\u2013235 (1986)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"1099_CR19","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0166-218X(02)00246-9","volume":"127","author":"T. Michael","year":"2003","unstructured":"Michael T., Quint T.: Sphere of influence graphs and the L \u221e-metric. Discrete Appl. Math. 127(3), 447\u2013460 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"8","key":"1099_CR20","doi-asserted-by":"crossref","first-page":"1309","DOI":"10.1016\/j.dam.2006.01.004","volume":"154","author":"T. Michael","year":"2006","unstructured":"Michael T., Quint T.: Sphericity, cubicity, and edge clique covers of graphs. Discrete Appl. Math. 154(8), 1309\u20131313 (2006)","journal-title":"Discrete Appl. Math."},{"key":"1099_CR21","unstructured":"Roberts, F.S.: On the boxicity and cubicity of a graph. In: Recent Progresses in Combinatorics, pp. 301\u2013310. Academic Press, Dublin (1969)"},{"issue":"1","key":"1099_CR22","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(1), 127\u2013136 (2007)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"2","key":"1099_CR23","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/0215041","volume":"15","author":"J. Turner","year":"1986","unstructured":"Turner J.: On the probable performance of heuristics for bandwidth minimization. SIAM J. Comput. 15(2), 561\u2013580 (1986)","journal-title":"SIAM J. Comput."},{"key":"1099_CR24","doi-asserted-by":"crossref","unstructured":"Unger, W.: The complexity of the approximation of the bandwidth problem. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 82\u201391. IEEE Computer Society (1998)","DOI":"10.1109\/SFCS.1998.743431"},{"key":"1099_CR25","doi-asserted-by":"crossref","unstructured":"van Leeuwen, E.J.: Approximation algorithms for unit disk graphs. In: Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), LNCS, vol. 3787, pp. 351\u2013361 (2005)","DOI":"10.1007\/11604686_31"},{"issue":"3","key":"1099_CR26","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(3), 351\u2013358 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-011-1099-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-011-1099-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-011-1099-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,13]],"date-time":"2025-03-13T00:30:13Z","timestamp":1741825813000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-011-1099-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,19]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["1099"],"URL":"https:\/\/doi.org\/10.1007\/s00373-011-1099-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2011,10,19]]}}}