{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:35Z","timestamp":1759637615548,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030261757"},{"type":"electronic","value":"9783030261764"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-26176-4_18","type":"book-chapter","created":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T23:02:56Z","timestamp":1563922976000},"page":"219-231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Imbalance, Cutwidth, and the Structure of Optimal Orderings"],"prefix":"10.1007","author":[{"given":"Jan","family":"Gorzny","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan F.","family":"Buss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,21]]},"reference":[{"key":"18_CR1","unstructured":"Bakken, O.R.: Arrangement problems parameterized by neighbourhood diversity. Master\u2019s thesis, The University of Bergen (2018)"},{"issue":"1","key":"18_CR2","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.dam.2004.12.001","volume":"148","author":"T Biedl","year":"2005","unstructured":"Biedl, T., Chan, T., Ganjali, Y., Hajiaghayi, M.T., Wood, D.R.: Balanced vertex-orderings of graphs. Discrete Appl. Math. 148(1), 27\u201348 (2005)","journal-title":"Discrete Appl. Math."},{"key":"18_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandstadt","year":"1999","unstructured":"Brandstadt, A., Spinrad, J.P., et al.: Graph Classes: A Survey, vol. 3. SIAM, Philadelphia (1999)"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-319-71147-8_11","volume-title":"Combinatorial Optimization and Applications","author":"P Charbit","year":"2017","unstructured":"Charbit, P., Habib, M., Mouatadid, L., Naserasr, R.: A new graph parameter to measure linearity. In: Gao, X., Du, H., Han, M. (eds.) COCOA 2017. LNCS, vol. 10628, pp. 154\u2013168. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-71147-8_11"},{"issue":"3","key":"18_CR5","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.dam.2003.07.001","volume":"138","author":"DG Corneil","year":"2004","unstructured":"Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discrete Appl. Math. 138(3), 371\u2013379 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"18_CR6","doi-asserted-by":"publisher","first-page":"1905","DOI":"10.1137\/S0895480100373455","volume":"23","author":"DG Corneil","year":"2009","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: The LBFS structure and recognition of interval graphs. SIAM J. Discrete Math. 23(4), 1905\u20131953 (2009)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"18_CR7","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1007\/s00453-012-9707-6","volume":"68","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Lokshtanov, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: On cutwidth parameterized by vertex cover. Algorithmica 68(4), 940\u2013953 (2014)","journal-title":"Algorithmica"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","author":"MR Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 294\u2013305. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-92182-0_28"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-319-03898-8_15","volume-title":"Parameterized and Exact Computation","author":"J Gajarsk\u00fd","year":"2013","unstructured":"Gajarsk\u00fd, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 163\u2013176. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_15"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-642-28050-4_21","volume-title":"Parameterized and Exact Computation","author":"R Ganian","year":"2012","unstructured":"Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 259\u2013271. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28050-4_21"},{"issue":"10","key":"18_CR11","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1016\/j.ipl.2009.01.003","volume":"109","author":"S Gaspers","year":"2009","unstructured":"Gaspers, S., Messinger, M.-E., Nowakowski, R.J., Pra\u0142at, P.: Clean the graph before you draw it!. Inf. Process. Lett. 109(10), 463\u2013467 (2009)","journal-title":"Inf. Process. Lett."},{"key":"18_CR12","unstructured":"Giannopoulou, A.C., Pilipczuk, M., Raymond, J.-F., Thilikos, D.M., Wrochna, M.: Cutwidth: obstructions and algorithmic aspects. arXiv preprint arXiv:1606.05975 (2016)"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-540-92248-3_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P Heggernes","year":"2008","unstructured":"Heggernes, P., Lokshtanov, D., Mihai, R., Papadopoulos, C.: Cutwidth of split graphs, threshold graphs, and proper interval graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 218\u2013229. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-92248-3_20"},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-16926-7_9","volume-title":"Graph Theoretic Concepts in Computer Science","author":"P Heggernes","year":"2010","unstructured":"Heggernes, P., van \u2019t Hof, P., Lokshtanov, D., Nederlof, J.: Computing the cutwidth of bipartite permutation graphs in linear time. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 75\u201387. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16926-7_9"},{"issue":"2","key":"18_CR15","first-page":"50","volume":"7","author":"Y Jinjiang","year":"1994","unstructured":"Jinjiang, Y., Liying, K.: One characterization of unit interval graphs and its applications. J. Shijiazhuang Railway Inst. 7(2), 50\u201354 (1994)","journal-title":"J. Shijiazhuang Railway Inst."},{"issue":"3","key":"18_CR16","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF02662875","volume":"10","author":"Y Jinjiang","year":"1995","unstructured":"Jinjiang, Y., Sanming, Z.: Optimal labelling of unit interval graphs. Appl. Math. 10(3), 337\u2013344 (1995)","journal-title":"Appl. Math."},{"issue":"1","key":"18_CR17","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1007\/BF02086606","volume":"16","author":"G Kant","year":"1996","unstructured":"Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4\u201332 (1996)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"18_CR18","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0304-3975(95)00257-X","volume":"172","author":"G Kant","year":"1997","unstructured":"Kant, G., He, X.: Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoret. Comput. Sci. 172(1\u20132), 175\u2013193 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"18_CR19","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C Lekkerkerker","year":"1962","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)","journal-title":"Fund. Math."},{"key":"18_CR20","unstructured":"Lilleeng, S.: A polynomial-time solvable case for the NP-hard problem cutwidth. Master\u2019s thesis, The University of Bergen (2014)"},{"issue":"19\u201321","key":"18_CR21","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1016\/j.ipl.2013.06.010","volume":"113","author":"D Lokshtanov","year":"2013","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Imbalance is fixed parameter tractable. Inf. Process. Lett. 113(19\u201321), 714\u2013718 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"18_CR22","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0925-7721(97)00017-5","volume":"9","author":"A Papakostas","year":"1998","unstructured":"Papakostas, A., Tollis, I.G.: Algorithms for area-efficient orthogonal drawings. Comput. Geom. 9(1\u20132), 83\u2013110 (1998)","journal-title":"Comput. Geom."},{"key":"18_CR23","unstructured":"Stephane, F., Hammer, P.L.: Split graphs. In: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 311\u2013315 (1977)"},{"issue":"1","key":"18_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M., Bodlaender, H.L.: Cutwidth I: a linear time fixed parameter algorithm. J. Algorithms 56(1), 1\u201324 (2005)","journal-title":"J. Algorithms"},{"issue":"1","key":"18_CR25","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jalgor.2004.12.003","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M., Bodlaender, H.L.: Cutwidth II: algorithms for partial w-trees of bounded degree. J. Algorithms 56(1), 25\u201349 (2005)","journal-title":"J. Algorithms"},{"key":"18_CR26","unstructured":"Wagner, G.: Eigenschaften der nerven homologische-einfactor familien in $$R^n$$. Ph.D. thesis, Universit\u00e4t Gottigen (1967)"},{"issue":"1\u20133","key":"18_CR27","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0304-3975(02)00044-0","volume":"299","author":"DR Wood","year":"2003","unstructured":"Wood, D.R.: Optimal three-dimensional orthogonal graph drawing in the general position model. Theoret. Comput. Sci. 299(1\u20133), 151\u2013178 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"18_CR28","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00453-004-1091-4","volume":"39","author":"DR Wood","year":"2004","unstructured":"Wood, D.R.: Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout. Algorithmica 39(3), 235\u2013253 (2004)","journal-title":"Algorithmica"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"Wood, D.R., Kratochvil, J., K\u00e1ra, J.: On the complexity of the balanced vertex ordering problem. Discrete Math. Theor. Comput. Sci. 9 (2007)","DOI":"10.46298\/dmtcs.383"},{"issue":"4","key":"18_CR30","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M Yannakakis","year":"1985","unstructured":"Yannakakis, M.: A polynomial algorithm for the min-cut linear arrangement of trees. J. ACM (JACM) 32(4), 950\u2013988 (1985)","journal-title":"J. ACM (JACM)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-26176-4_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T14:05:57Z","timestamp":1709820357000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-26176-4_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030261757","9783030261764"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-26176-4_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"21 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Xi'an","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2019a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ictt.xidian.edu.cn\/COCOON2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}