{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:52Z","timestamp":1761621112539},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642332920"},{"type":"electronic","value":"9783642332937"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33293-7_14","type":"book-chapter","created":{"date-parts":[[2012,8,29]],"date-time":"2012-08-29T10:50:58Z","timestamp":1346237458000},"page":"135-146","source":"Crossref","is-referenced-by-count":4,"title":["Polynomial Time and Parameterized Approximation Algorithms for Boxicity"],"prefix":"10.1007","author":[{"given":"Abhijin","family":"Adiga","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jasine","family":"Babu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. Sunil","family":"Chandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"1719","DOI":"10.1016\/j.dam.2010.06.017","volume":"158","author":"A. Adiga","year":"2010","unstructured":"Adiga, A., Bhowmick, D., Chandran, L.S.: The hardness of approximating the boxicity, cubicity and threshold dimension of a graph. Discrete Appl. Math.\u00a0158, 1719\u20131726 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"14_CR2","doi-asserted-by":"publisher","first-page":"1687","DOI":"10.1137\/100786290","volume":"25","author":"A. Adiga","year":"2011","unstructured":"Adiga, A., Bhowmick, D., Chandran, L.S.: Boxicity and poset dimension. SIAM J. Discrete Math.\u00a025(4), 1687\u20131698 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-642-17517-6_33","volume-title":"Algorithms and Computation","author":"A. Adiga","year":"2010","unstructured":"Adiga, A., Chitnis, R., Saurabh, S.: Parameterized Algorithms for Boxicity. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol.\u00a06506, pp. 366\u2013377. Springer, Heidelberg (2010)"},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci.\u00a013(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"14_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L. Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett.\u00a058(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"14_CR6","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L. Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Applied Mathematics\u00a0127(3), 415\u2013429 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"14_CR7","doi-asserted-by":"publisher","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\u00a097, 733\u2013744 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"key":"14_CR8","unstructured":"Cozzens, M.B.: Higher and multi-dimensional analogues of interval graphs. Ph.D. thesis, Department of Mathematics, Rutgers University, New Brunswick, NJ (1981)"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-642-11269-0_12","volume-title":"Parameterized and Exact Computation","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A.: Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 149\u2013160. Springer, Heidelberg (2009)"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/j.jcss.2003.07.008","volume":"68","author":"M. Grohe","year":"2004","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. J. Comput. Syst. Sci.\u00a068, 285\u2013302 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"14_CR11","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J. Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Discrete Appl. Math.\u00a052(3), 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"14_CR12","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/j.tcs.2005.10.008","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized coloring problems on chordal graphs. Theor. Comput. Sci.\u00a0351(3), 407\u2013424 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"3-4","key":"14_CR13","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1007\/s00453-010-9484-z","volume":"62","author":"D. Marx","year":"2012","unstructured":"Marx, D., Schlotter, I.: Obtaining a planar graph by vertex deletion. Algorithmica\u00a062(3-4), 807\u2013822 (2012)","journal-title":"Algorithmica"},{"key":"14_CR14","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms (2002)"},{"key":"14_CR15","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 Press, New York (1969)"},{"key":"14_CR16","first-page":"127","volume":"9","author":"B. Rosgen","year":"2007","unstructured":"Rosgen, B., Stewart, L.: Complexity results on graphs with few cliques. Discrete Mathematics and Theoretical Computer Science\u00a09, 127\u2013136 (2007)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"14_CR17","doi-asserted-by":"publisher","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\u00a040, 9\u201320 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5","key":"14_CR18","doi-asserted-by":"publisher","first-page":"2007","DOI":"10.1137\/070710913","volume":"38","author":"Y. Villanger","year":"2008","unstructured":"Villanger, Y., Heggernes, P., Paul, C., Telle, J.A.: Interval completion is fixed parameter tractable. SIAM J. Comput.\u00a038(5), 2007\u20132020 (2008)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"14_CR19","doi-asserted-by":"publisher","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. Alg. Disc. Meth.\u00a03(3), 351\u2013358 (1982)","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33293-7_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:03:22Z","timestamp":1620129802000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33293-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642332920","9783642332937"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33293-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}