{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,13]],"date-time":"2026-11-13T08:37:44Z","timestamp":1794559064100,"version":"4.9.1"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319739144","type":"print"},{"value":"9783319739151","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73915-1_43","type":"book-chapter","created":{"date-parts":[[2018,1,19]],"date-time":"2018-01-19T22:42:19Z","timestamp":1516401739000},"page":"560-572","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Effect of Planarization on Width"],"prefix":"10.1007","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,1,21]]},"reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Leighton, F.T.: New lower bound techniques for VLSI. In: Proceedings of 22nd Symposium on Foundations of Computer Science (FOCS 1981), pp. 1\u201312. IEEE (1981)","DOI":"10.1109\/SFCS.1981.22"},{"key":"43_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-45848-4_5","volume-title":"Graph Drawing","author":"G Di Battista","year":"2002","unstructured":"Di Battista, G., Didimo, W., Marcandalli, A.: Planarization of clustered graphs. In: Mutzel, P., J\u00fcnger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 60\u201374. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45848-4_5"},{"key":"43_CR3","unstructured":"Buchheim, C., Chimani, M., Gutwenger, C., J\u00fcnger, M., Mutzel, P.: Crossings and planarization. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization. Discrete Mathematics and its Applications, pp. 43\u201386. CRC Press (2014)"},{"key":"43_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.2307\/2271520","volume":"36","author":"S Garfunkel","year":"1971","unstructured":"Garfunkel, S., Shank, H.: On the undecidability of finite planar graphs. J. Symb. Log. 36, 121\u2013126 (1971)","journal-title":"J. Symb. Log."},{"issue":"8","key":"43_CR5","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1109\/TCS.1986.1085997","volume":"33","author":"K Thulasiraman","year":"1986","unstructured":"Thulasiraman, K., Jayakumar, R., Swamy, M.N.S.: On maximal planarization of nonplanar graphs. IEEE Trans. Circ. Syst. 33(8), 843\u2013844 (1986)","journal-title":"IEEE Trans. Circ. Syst."},{"issue":"1","key":"43_CR6","first-page":"49","volume":"18","author":"R Cimikowski","year":"1997","unstructured":"Cimikowski, R.: An analysis of heuristics for graph planarization. J. Inform. Optim. Sci. 18(1), 49\u201373 (1997)","journal-title":"J. Inform. Optim. Sci."},{"key":"43_CR7","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Makarychev, Y., Sidiropoulos, A.: On graph crossing number and edge planarization. In: Randall, D. (ed.) Proceedings of 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). Society for Industrial and Applied Mathematics, pp. 1050\u20131069 (2011)","DOI":"10.1137\/1.9781611973082.80"},{"issue":"1","key":"43_CR8","doi-asserted-by":"publisher","first-page":"281","DOI":"10.7155\/jgaa.00358","volume":"19","author":"G Borradaile","year":"2015","unstructured":"Borradaile, G., Eppstein, D., Zhu, P.: Planar induced subgraphs of sparse graphs. J. Graph Algorithms Appl. 19(1), 281\u2013297 (2015)","journal-title":"J. Graph Algorithms Appl."},{"key":"43_CR9","unstructured":"Jansen, B.M.P., Wulms, J.J.H.M.: Lower bounds for protrusion replacement by counting equivalence classes. In: Guo, J., Hermelin, D. (eds.) Proceedings of 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, vol. 63, pp. 17:1\u201317:12 (2016)"},{"key":"43_CR10","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity. Graphs, Structures, and Algorithms","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity. Graphs, Structures, and Algorithms. AC, vol. 28. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4"},{"issue":"6","key":"43_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"NG Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Inform. Process. Lett. 42(6), 345\u2013350 (1992)","journal-title":"Inform. Process. Lett."},{"issue":"1\u20133","key":"43_CR12","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0012-365X(89)90083-6","volume":"75","author":"FRK Chung","year":"1989","unstructured":"Chung, F.R.K., Seymour, P.D.: Graphs with small bandwidth and cutwidth. Discrete Math. 75(1\u20133), 113\u2013119 (1989)","journal-title":"Discrete Math."},{"issue":"2","key":"43_CR13","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"issue":"4","key":"43_CR14","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"key":"43_CR15","doi-asserted-by":"publisher","first-page":"137","DOI":"10.4064\/fm-41-1-137-145","volume":"41","author":"K Zarankiewicz","year":"1954","unstructured":"Zarankiewicz, K.: On a problem of P. Turan concerning graphs. Fund. Math. 41, 137\u2013145 (1954)","journal-title":"Fund. Math."},{"key":"43_CR16","doi-asserted-by":"crossref","unstructured":"Pach, J., T\u00f3th, G.: Which crossing number is it, anyway? In: Motwani, R. (ed.) Proceedings of 39th Symposium on Foundations of Computer Science (FOCS 1998), pp. 617\u2013626. IEEE (1998)","DOI":"10.1109\/SFCS.1998.743512"},{"key":"43_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0021-9800(70)80087-4","volume":"9","author":"DJ Kleitman","year":"1970","unstructured":"Kleitman, D.J.: The crossing number of $$K_{5, n}$$. J. Comb. Theory 9, 315\u2013323 (1970)","journal-title":"J. Comb. Theory"},{"key":"43_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/3-540-40064-8_19","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F Gurski","year":"2000","unstructured":"Gurski, F., Wanke, E.: The tree-width of clique-width bounded graphs without $$K{_{n,n}}$$. In: Brandes, U., Wagner, D. (eds.) WG 2000. LNCS, vol. 1928, pp. 196\u2013205. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-40064-8_19"},{"key":"43_CR19","unstructured":"Eppstein, D.: The effect of planarization on width. Electronic preprint arxiv:1708.05155 (2017)"},{"key":"43_CR20","unstructured":"van Geffen, B.A.M., Jansen, B.M.P., de Kroon, N.A.W.M., Morel, R., Nederlof, J.: Optimal algorithms on graphs of bounded width (and degree): cutwidth sometimes beats treewidth, but planarity does not help. Manuscript (2017)"},{"issue":"1","key":"43_CR21","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0022-0000(89)90038-X","volume":"38","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38(1), 165\u2013194 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"43_CR22","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.dam.2013.05.026","volume":"168","author":"NV Nestoridis","year":"2014","unstructured":"Nestoridis, N.V., Thilikos, D.M.: Square roots of minor closed graph classes. Discrete Appl. Math. 168, 34\u201339 (2014)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing and Network Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73915-1_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T19:09:20Z","timestamp":1751224160000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-73915-1_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319739144","9783319739151"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73915-1_43","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-319-73915-1","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"21 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"GD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Graph Drawing and Network Visualization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Boston","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 September 2017","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":"gd2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/gd2017.ccis.northeastern.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}