{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T05:33:05Z","timestamp":1774503185714,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,6,4]],"date-time":"2015-06-04T00:00:00Z","timestamp":1433376000000},"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":["Algorithmica"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00453-015-0011-0","type":"journal-article","created":{"date-parts":[[2015,6,4]],"date-time":"2015-06-04T01:03:21Z","timestamp":1433379801000},"page":"1453-1472","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Structural Parameterizations for Boxicity"],"prefix":"10.1007","volume":"74","author":[{"given":"Henning","family":"Bruhn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morgan","family":"Chopin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felix","family":"Joos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,4]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Adiga, A., Babu, J., Chandran, L.S.: Polynomial time and parameterized approximation algorithms for boxicity. In: Proceedings of the 7th International Symposium on Algorithms and Computation (IPEC 2012), LNCS 7535, pp. 135\u2013146 (2012)","DOI":"10.1007\/978-3-642-33293-7_14"},{"issue":"16","key":"11_CR2","doi-asserted-by":"crossref","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. 158(16), 1719\u20131726 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"11_CR3","doi-asserted-by":"crossref","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. 25(4), 1687\u20131698 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Adiga, A., Chitnis, R., Saurabh, S.: Parameterized algorithms for boxicity. In: Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), LNCS 6506, pp. 366\u2013377 (2010)","DOI":"10.1007\/978-3-642-17517-6_33"},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"181","DOI":"10.7146\/math.scand.a-10607","volume":"8","author":"E Asplund","year":"1960","unstructured":"Asplund, E., Gr\u00fcnbaum, B.: On a coloring problem. Math. Scand 8, 181\u2013188 (1960)","journal-title":"Math. Scand"},{"key":"11_CR6","first-page":"333","volume":"1","author":"A Bielecki","year":"1948","unstructured":"Bielecki, A.: Problem 56. Colloq. Math. 1, 333 (1948)","journal-title":"Colloq. Math."},{"issue":"6","key":"11_CR7","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"11_CR8","doi-asserted-by":"crossref","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. 58(4), 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Graph products revisited: tight approximation hardness of induced matching, poset dimension and more. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1557\u20131576 (2013)","DOI":"10.1137\/1.9781611973105.112"},{"issue":"5","key":"11_CR10","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1016\/j.jctb.2006.12.004","volume":"97","author":"LS 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":"11_CR11","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"11_CR12","unstructured":"Cozzens, M.: Higher and multi-dimensional analogues of interval graphs. Ph.d. thesis, Department of Mathematics, Rutgers University, New Brunswick (1981)"},{"key":"11_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory, 4th edn. Springer, Berlin (2010)","edition":"4"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Doucha, M., Kratochv\u00edl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012), LNCS 7464, pp. 348\u2013359 (2012)","DOI":"10.1007\/978-3-642-32589-2_32"},{"key":"11_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"issue":"1","key":"11_CR16","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00453-011-9545-y","volume":"64","author":"MR Fellows","year":"2012","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A.: Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications. Algorithmica 64(1), 3\u201318 (2012)","journal-title":"Algorithmica"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: Proceedings of the 6th International Symposium on Algorithms and Computation (IPEC 2011), LNCS 7112, pp. 259\u2013271 (2011)","DOI":"10.1007\/978-3-642-28050-4_21"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Kostochka, A.: Coloring intersection graphs of geometric figures with a given clique number. In: Pach, J, (ed.) Towards A Theory of Geometric Graphs, vol. 342 of Contemp. Math., pp. 127\u2013138. Amer. Math. Soc. (2004)","DOI":"10.1090\/conm\/342\/06137"},{"issue":"3","key":"11_CR19","doi-asserted-by":"crossref","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. 52(3), 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Lekkerkerker, C., Boland, J.: Representation of a finite graph by a set of intervals on the real line. Fund. Math. 51(1), 45\u201364 (1962\/1963)","DOI":"10.4064\/fm-51-1-45-64"},{"key":"11_CR21","unstructured":"Roberts, F.S.: On the boxicity and cubicity of a graph. In: Recent Progresses in Combinatorics, pp. 301\u2013310. Academic Press (1969)"},{"key":"11_CR22","unstructured":"Scheinerman, E.: Intersection classes and multiple intersection parameters. Ph.D. thesis, Princeton University (1984)"},{"key":"11_CR23","doi-asserted-by":"crossref","DOI":"10.1090\/fim\/019","volume-title":"Efficient Graph Representations","author":"J Spinrad","year":"2003","unstructured":"Spinrad, J.: Efficient Graph Representations. American Mathematical Society, Fields Institute monographs, Providence (2003)"},{"issue":"1","key":"11_CR24","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(1), 9\u201320 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"11_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. Algebr. Discrete Methods 3(3), 351\u2013358 (1982)","journal-title":"SIAM J. Algebr. Discrete Methods"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0011-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0011-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0011-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,25]],"date-time":"2019-08-25T23:20:07Z","timestamp":1566775207000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0011-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,4]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["11"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0011-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,4]]}}}