{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:02:41Z","timestamp":1743058961551,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030358013"},{"type":"electronic","value":"9783030358020"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[[2019]]},"DOI":"10.1007\/978-3-030-35802-0_28","type":"book-chapter","created":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T23:02:50Z","timestamp":1574895770000},"page":"365-378","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Algorithms for Book Embedding Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0104-1659","authenticated-orcid":false,"given":"Sujoy","family":"Bhore","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7762-8045","authenticated-orcid":false,"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0543-8912","authenticated-orcid":false,"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,28]]},"reference":[{"issue":"1","key":"28_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.7155\/jgaa.00457","volume":"22","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. 22(1), 23\u201349 (2018). https:\/\/doi.org\/10.7155\/jgaa.00457","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"28_CR2","doi-asserted-by":"publisher","first-page":"577","DOI":"10.7155\/jgaa.00479","volume":"22","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. J. Graph Algorithms Appl. 22(4), 577\u2013606 (2018). https:\/\/doi.org\/10.7155\/jgaa.00479","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"28_CR3","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/s00453-015-0016-8","volume":"75","author":"MA Bekos","year":"2016","unstructured":"Bekos, M.A., Gronemann, M., Raftopoulou, C.N.: Two-page book embeddings of 4-planar graphs. Algorithmica 75(1), 158\u2013185 (2016). https:\/\/doi.org\/10.1007\/s00453-015-0016-8","journal-title":"Algorithmica"},{"issue":"3","key":"28_CR4","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F Bernhart","year":"1979","unstructured":"Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory Ser. B 27(3), 320\u2013331 (1979). https:\/\/doi.org\/10.1016\/0095-8956(79)90021-2","journal-title":"J. Comb. Theory Ser. B"},{"key":"28_CR5","unstructured":"Bhore, S., Ganian, R., Montecchiani, F., N\u00f6llenburg, M.: Parameterized algorithms for book embedding problems. CoRR abs\/1908.08911 (2019). http:\/\/arxiv.org\/abs\/1908.08911"},{"key":"28_CR6","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.ejc.2017.07.009","volume":"68","author":"C Binucci","year":"2018","unstructured":"Binucci, C., Di Giacomo, E., Hossain, M.I., Liotta, G.: 1-page and 2-page drawings with bounded number of crossings per edge. Eur. J. Comb. 68, 24\u201337 (2018). https:\/\/doi.org\/10.1016\/j.ejc.2017.07.009","journal-title":"Eur. J. Comb."},{"issue":"40\u201342","key":"28_CR7","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.06.026","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"28_CR8","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"F Chung","year":"1987","unstructured":"Chung, F., Leighton, F., Rosenberg, A.: Embedding graphs in books: a layout problem with applications to VLSI design. SIAM J. Algebraic Discret. Methods 8(1), 33\u201358 (1987). https:\/\/doi.org\/10.1137\/0608002","journal-title":"SIAM J. Algebraic Discret. Methods"},{"key":"28_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"28_CR10","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2012)"},{"key":"28_CR11","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","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. TCS. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"issue":"2","key":"28_CR12","first-page":"339","volume":"6","author":"V Dujmovi\u0107","year":"2004","unstructured":"Dujmovi\u0107, V., Wood, D.R.: On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6(2), 339\u2013358 (2004)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"4","key":"28_CR13","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00454-007-1318-7","volume":"37","author":"V Dujmovic","year":"2007","unstructured":"Dujmovic, V., Wood, D.R.: Graph treewidth and geometric thickness parameters. Discrete Comput. Geom. 37(4), 641\u2013670 (2007). https:\/\/doi.org\/10.1007\/s00454-007-1318-7","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"28_CR14","first-page":"39","volume":"13","author":"V Dujmovi\u0107","year":"2011","unstructured":"Dujmovi\u0107, V., Wood, D.R.: On the book thickness of k-trees. Discrete Math. Theor. Comput. Sci. 13(3), 39\u201344 (2011)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"28_CR15","doi-asserted-by":"publisher","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Algorithms and Computation (ISAAC 2008), pp. 294\u2013305 (2008). https:\/\/doi.org\/10.1007\/978-3-540-92182-0_28","DOI":"10.1007\/978-3-540-92182-0_28"},{"issue":"2","key":"28_CR16","first-page":"77","volume":"17","author":"R Ganian","year":"2015","unstructured":"Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2), 77\u2013100 (2015)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"28_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.artint.2017.12.006","volume":"257","author":"R Ganian","year":"2018","unstructured":"Ganian, R., Ordyniak, S.: The complexity landscape of decompositional parameters for ILP. Artif. Intell. 257, 61\u201371 (2018). https:\/\/doi.org\/10.1016\/j.artint.2017.12.006","journal-title":"Artif. Intell."},{"issue":"3","key":"28_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0166-218X(00)00178-5","volume":"109","author":"JL Ganley","year":"2001","unstructured":"Ganley, J.L., Heath, L.S.: The pagenumber of $$k$$-trees is $$O(k)$$. Discrete Appl. Math. 109(3), 215\u2013221 (2001). https:\/\/doi.org\/10.1016\/S0166-218X(00)00178-5","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"28_CR19","doi-asserted-by":"publisher","first-page":"2177","DOI":"10.1137\/15M1034337","volume":"30","author":"GZ Gutin","year":"2016","unstructured":"Gutin, G.Z., Jones, M., Wahlstr\u00f6m, M.: The mixed Chinese postman problem parameterized by pathwidth and treedepth. SIAM J. Discrete Math. 30(4), 2177\u20132205 (2016). https:\/\/doi.org\/10.1137\/15M1034337","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"28_CR20","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1006\/bulm.1998.0085","volume":"61","author":"C Haslinger","year":"1999","unstructured":"Haslinger, C., Stadler, P.F.: RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties. Bull. Math. Biol. 61(3), 437\u2013467 (1999). https:\/\/doi.org\/10.1006\/bulm.1998.0085","journal-title":"Bull. Math. Biol."},{"key":"28_CR21","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BFb0066436","volume-title":"Graphs and Combinatorics","author":"PC Kainen","year":"1974","unstructured":"Kainen, P.C.: Some recent results in topological graph theory. In: Bari, R.A., Harary, F. (eds.) Graphs and Combinatorics, pp. 76\u2013108. Springer, Berlin (1974). https:\/\/doi.org\/10.1007\/BFb0066436"},{"issue":"6","key":"28_CR22","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. Inf. Process. Lett. 42(6), 345\u2013350 (1992). https:\/\/doi.org\/10.1016\/0020-0190(92)90234-M","journal-title":"Inf. Process. Lett."},{"key":"28_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/978-3-319-66263-3_27","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2017","author":"N Lodha","year":"2017","unstructured":"Lodha, N., Ordyniak, S., Szeider, S.: SAT-encodings for special treewidth and pathwidth. In: Gaspers, S., Walsh, T. (eds.) SAT 2017. LNCS, vol. 10491, pp. 429\u2013445. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-66263-3_27"},{"key":"28_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-319-78825-8_27","volume-title":"Combinatorial Algorithms","author":"S Mallach","year":"2018","unstructured":"Mallach, S.: Linear ordering based MIP formulations for the vertex separation or pathwidth problem. In: Brankovic, L., Ryan, J., Smyth, W.F. (eds.) IWOCA 2017. LNCS, vol. 10765, pp. 327\u2013340. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78825-8_27"},{"key":"28_CR25","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity. AC, vol. 28. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4"},{"key":"28_CR26","unstructured":"Ollmann, L.T.: On the book thicknesses of various graphs. In: 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, vol. 8, p. 459 (1973)"},{"issue":"1","key":"28_CR27","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory Ser. B 35(1), 39\u201361 (1983). https:\/\/doi.org\/10.1016\/0095-8956(83)90079-5","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"28_CR28","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4","journal-title":"J. Algorithms"},{"key":"28_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/3-540-55210-3_199","volume-title":"STACS 92","author":"W Unger","year":"1992","unstructured":"Unger, W.: The complexity of colouring circle graphs. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol. 577, pp. 389\u2013400. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/3-540-55210-3_199. (extended abstract)"},{"issue":"1","key":"28_CR30","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M Yannakakis","year":"1989","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36\u201367 (1989). https:\/\/doi.org\/10.1016\/0022-0000(89)90032-9","journal-title":"J. Comput. Syst. Sci."}],"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-030-35802-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T01:04:47Z","timestamp":1701133487000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-35802-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030358013","9783030358020"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-35802-0_28","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":"28 November 2019","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":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","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":"17 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 September 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/kam.mff.cuni.cz\/gd2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"113","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.11","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12.55","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}