{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,24]],"date-time":"2025-12-24T14:44:40Z","timestamp":1766587480261},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2014,6,26]],"date-time":"2014-06-26T00:00:00Z","timestamp":1403740800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2014,12]]},"DOI":"10.1007\/s00493-011-2981-0","type":"journal-article","created":{"date-parts":[[2014,6,26]],"date-time":"2014-06-26T11:51:50Z","timestamp":1403783510000},"page":"631-655","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Lower bounds for boxicity"],"prefix":"10.1007","volume":"34","author":[{"given":"Abhijin","family":"Adiga","sequence":"first","affiliation":[]},{"given":"L. Sunil","family":"Chandran","sequence":"additional","affiliation":[]},{"given":"Naveen","family":"Sivadasan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,6,26]]},"reference":[{"key":"2981_CR1","volume-title":"WADS, vol. 6844 of Lecture Notes in Computer Science","author":"A. Adiga","year":"2011","unstructured":"A. Adiga, J. Babu and L. S. Chandran: A constant factor approximation algorithm for boxicity of circular arc graphs, in: F. Dehne, J. Iacono, J.-R. Sack (eds.), WADS, vol. 6844 of Lecture Notes in Computer Science, Springer, 2011."},{"key":"2981_CR2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"N. Alon: Eigenvalues and expanders, Combinatorica 6 (1986), 83\u201396.","journal-title":"Combinatorica"},{"key":"2981_CR3","volume-title":"The probabilistic method","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. H. Spencer and P. Erd\u00f6s: The probabilistic method, John Wiley & Sons, Inc., 1992."},{"key":"2981_CR4","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0012-365X(93)90354-V","volume":"114","author":"S. Bellantoni","year":"1993","unstructured":"S. Bellantoni, I. B.-A. Hartman, T. Przytycka and S. Whitesides: Grid intersection graphs and boxicity, Disc. Math. 114) (1993), 41\u201349.","journal-title":"Disc. Math."},{"key":"2981_CR5","first-page":"333","volume":"1","author":"A. Bielecki","year":"1948","unstructured":"A. Bielecki: Problem 56, Colloq. Math 1 (1948), 333.","journal-title":"Colloq. Math"},{"key":"2981_CR6","volume-title":"Algebraic Graph theory","author":"N. Biggs","year":"1993","unstructured":"N. Biggs: Algebraic Graph theory, Cambridge University Press Cambridge, 1993."},{"key":"2981_CR7","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/j.jctb.2005.04.005","volume":"95","author":"Y. Bilu","year":"2005","unstructured":"Y. Bilu and N. Linial: Monotone maps, sphericity and bounded second eigenvalue, J. Comb. Theory Ser. B 95 (2005), 283\u2013299.","journal-title":"J. Comb. Theory Ser. B"},{"key":"2981_CR8","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"B. Bollob\u00e1s: Random graphs, Cambridge university press, 2001."},{"key":"2981_CR9","volume-title":"Combinatorics","author":"B. Bollob\u00e1s","year":"1986","unstructured":"B. Bollob\u00e1s: Combinatorics, Cambridge University Press, 1986."},{"key":"2981_CR10","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/j.jctb.2007.08.002","volume":"98","author":"L. S. Chandran","year":"2008","unstructured":"L. S. Chandran, M. C. Francis and N. Sivadasan: Boxicity and maximum degree, J. Comb. Theory Ser. B 98 (2008), 443\u2013445.","journal-title":"J. Comb. Theory Ser. B"},{"key":"2981_CR11","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1016\/j.jctb.2006.12.004","volume":"97","author":"L. S. Chandran","year":"2007","unstructured":"L. S. Chandran and N. Sivadasan: Boxicity and treewidth, J. Comb. Theory Ser. B 97 (2007), 733\u2013744.","journal-title":"J. Comb. Theory Ser. B"},{"key":"2981_CR12","volume-title":"Proceedings of the 8th International Graph Theory Conf.","author":"Y. W. Chang","year":"1998","unstructured":"Y. W. Chang and D. B. West: Interval number and boxicity of digraphs, in: Proceedings of the 8th International Graph Theory Conf., 1998."},{"key":"2981_CR13","unstructured":"Y. W. Chang and D. B. West: Rectangle number for hyper cubes and complete multipartite graphs, in: 29th SE conf. Comb., Graph Th. and Comp., Congr. Numer. 132, 1998."},{"key":"2981_CR14","volume-title":"Higher and multi-dimensional analogues of interval graphs","author":"M. B. Cozzens","year":"1981","unstructured":"M. B. Cozzens: Higher and multi-dimensional analogues of interval graphs, Ph.D. thesis, Department of Mathematics, Rutgers University New Brunswick, NJ (1981)."},{"key":"2981_CR15","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0166-218X(83)90077-X","volume":"6","author":"M. B. Cozzens","year":"1983","unstructured":"M. B. Cozzens and F. S. Roberts: Computing the boxicity of a graph by covering its complement by cointerval graphs, Disc. Appl. Math. 6 (1983), 217\u2013228.","journal-title":"Disc. Appl. Math."},{"key":"2981_CR16","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0012-365X(79)90149-3","volume":"25","author":"R. B. Feinberg","year":"1979","unstructured":"R. B. Feinberg: The circular dimension of a graph, Disc. Math. 25 (1979), 27\u201331.","journal-title":"Disc. Math."},{"key":"2981_CR17","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0095-8956(83)90057-6","volume":"35","author":"P. C. Fishburn","year":"1983","unstructured":"P. C. Fishburn: On the sphericity and cubicity of graphs, J. Comb. Theory Ser. B 35 (1983), 309\u2013308.","journal-title":"J. Comb. Theory Ser. B"},{"key":"2981_CR18","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R. J. Fowler","year":"1981","unstructured":"R. J. Fowler, M. S. Paterson and S. L. Tanimoto: Optimal packing and covering in the plane are NP-complete, Information Processing letters 12 (1981), 133\u2013137.","journal-title":"Information Processing letters"},{"key":"2981_CR19","unstructured":"J. Friedman: A proof of Alon\u2019s second eigenvalue conjecture, accepted to the Memoirs of the A.M.S."},{"key":"2981_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511616679","volume-title":"Global methods for combinatorial isoperimetric problems","author":"L. H. Harper","year":"2004","unstructured":"L. H. Harper: Global methods for combinatorial isoperimetric problems, Cambridge University Press Cambridge, 2004."},{"key":"2981_CR21","volume-title":"The combinatorial distance geometry approach to the calculation of molecular conformation","author":"T. F. Havel","year":"1982","unstructured":"T. F. Havel: The combinatorial distance geometry approach to the calculation of molecular conformation, Ph.D. thesis, University of California Berkeley (1982)."},{"key":"2981_CR22","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0196-6774(83)90012-3","volume":"4","author":"H. Imai","year":"1983","unstructured":"H. Imai and T. Asano: Finding the connected component and a maximum clique of an intersection graph of rectangles in the plane, Journal of algorithms 4 (1983), 310\u2013323.","journal-title":"Journal of algorithms"},{"key":"2981_CR23","volume-title":"Expander codes","author":"N. Kahale","year":"1993","unstructured":"N. Kahale: Expander codes, Ph.D. thesis, MIT (1993)."},{"key":"2981_CR24","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1090\/conm\/342\/06137","volume":"342","author":"A. Kostochka","year":"2004","unstructured":"A. Kostochka: Coloring intersection graphs of geometric figures with a given clique number, Contemporary mathematics 342 (2004), 127\u2013138.","journal-title":"Contemporary mathematics"},{"key":"2981_CR25","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J. Kratochv\u00edl","year":"1994","unstructured":"J. Kratochv\u00edl: A special planar satisfiability problem and a consequence of its NP-completeness, Disc. Appl. Math. 52 (1994), 233\u2013252.","journal-title":"Disc. Appl. Math."},{"key":"2981_CR26","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01864152","volume":"4","author":"H. Maehara","year":"1988","unstructured":"H. Maehara, J. Reiterman, V. R\u00f6dl and E. \u0160i\u0148ajov\u00e1: Embedding of trees in euclidean spaces, Graphs and combinatorics 4 (1988), 43\u201347.","journal-title":"Graphs and combinatorics"},{"key":"2981_CR27","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/jgt.3190170210","volume":"17","author":"T. A. McKee","year":"1993","unstructured":"T. A. McKee and E. R. Scheinerman: On the chordality of a graph, Journal of Graph Theory 17 (1993), 221\u2013232.","journal-title":"Journal of Graph Theory"},{"key":"2981_CR28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and computing","author":"M. Mitzenmacher","year":"2005","unstructured":"M. Mitzenmacher and E. Upfal: Probability and computing, Cambridge University Press Cambridge, 2005."},{"key":"2981_CR29","first-page":"301","volume-title":"On the boxicity and cubicity of a graph","author":"F. S. Roberts","year":"1969","unstructured":"F. S. Roberts: Recent Progresses in Combinatorics, chap. On the boxicity and cubicity of a graph, Academic Press New York, 1969, 301\u2013310."},{"key":"2981_CR30","volume-title":"Intersection classes and multiple intersection parameters","author":"E. R. cheinerman","year":"1984","unstructured":"E. R. cheinerman: Intersection classes and multiple intersection parameters, Ph.D. thesis, Princeton University (1984)."},{"key":"2981_CR31","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0012-365X(90)90290-X","volume":"29","author":"J. B. Shearer","year":"1980","unstructured":"J. B. Shearer: A note on circular dimension, Disc. Math. 29 (1980), 103\u2013103.","journal-title":"Disc. Math."},{"key":"2981_CR32","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0605030","volume":"5","author":"R. M. Tanner","year":"1984","unstructured":"R. M. Tanner: Explicit construction of concentrators from generalized n-gons, SIAM J. Algebraic discrete methods 5 (1984), 287\u2013294.","journal-title":"SIAM J. Algebraic discrete methods"},{"key":"2981_CR33","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0095-8956(86)90061-4","volume":"40","author":"C. Thomassen","year":"1986","unstructured":"C. Thomassen: Interval representations of planar graphs, J. Comb. Theory Ser. B 40 (1986), 9\u201320.","journal-title":"J. Comb. Theory Ser. B"},{"key":"2981_CR34","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0012-365X(79)90137-7","volume":"28","author":"W. T. Trotter Jr.","year":"1979","unstructured":"W. T. Trotter, Jr.: A forbidden subgraph characterization of Roberts\u2019 inequality for boxicity, Disc. Math. 28 (1979), 303\u2013314.","journal-title":"Disc. Math."},{"key":"2981_CR35","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0012-365X(87)90247-0","volume":"64","author":"W. T. Trotter Jr.","year":"1987","unstructured":"W. T. Trotter, Jr. and D. B. West: Poset boxicity of graphs, Disc. Math. 64 (1987), 105\u2013107.","journal-title":"Disc. Math."},{"key":"2981_CR36","first-page":"239","volume-title":"Surveys in combinatorics","author":"N. C. Wormald","year":"1999","unstructured":"N. C. Wormald: Surveys in combinatorics, 1999 (Canterbury), chap. Models of random graphs, Cambridge Univ. Press Cambridge, 1999, 239\u2013298."},{"key":"2981_CR37","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF01275671","volume":"11","author":"B. D. McKay","year":"1991","unstructured":"B. D. McKay and N. C. Wormald: Asymptotic Enumeration By Degree Sequence of Graphs With Degrees o(n 1\/2), Combinatorica 11 (1991), 369\u2013382.","journal-title":"Combinatorica"},{"key":"2981_CR38","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"M. Yannakakis: The complexity of the partial order dimension problem, SIAM J. Alg. Disc. Math. 3 (1982), 351\u2013358.","journal-title":"SIAM J. Alg. Disc. Math."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-011-2981-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-011-2981-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-011-2981-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T21:32:48Z","timestamp":1559079168000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-011-2981-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,26]]},"references-count":38,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["2981"],"URL":"https:\/\/doi.org\/10.1007\/s00493-011-2981-0","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,26]]}}}