{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:49:03Z","timestamp":1767340143970,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030687656"},{"type":"electronic","value":"9783030687663"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-68766-3_4","type":"book-chapter","created":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T09:11:53Z","timestamp":1613293913000},"page":"40-54","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Parameterized Algorithms for Queue Layouts"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0104-1659","authenticated-orcid":false,"given":"Sujoy","family":"Bhore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7762-8045","authenticated-orcid":false,"given":"Robert","family":"Ganian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0543-8912","authenticated-orcid":false,"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,14]]},"reference":[{"issue":"4","key":"4_CR1","doi-asserted-by":"publisher","first-page":"1561","DOI":"10.1007\/s00453-018-0487-5","volume":"81","author":"MJ Bannister","year":"2018","unstructured":"Bannister, M.J., Devanny, W.E., Dujmovi\u0107, V., Eppstein, D., Wood, D.R.: Track layouts, layered path decompositions, and leveled planarity. Algorithmica 81(4), 1561\u20131583 (2018). https:\/\/doi.org\/10.1007\/s00453-018-0487-5","journal-title":"Algorithmica"},{"issue":"5","key":"4_CR2","doi-asserted-by":"publisher","first-page":"1487","DOI":"10.1137\/19M125340X","volume":"48","author":"MA Bekos","year":"2019","unstructured":"Bekos, M.A., et al.: Planar graphs of bounded degree have bounded queue number. SIAM J. Comput. 48(5), 1487\u20131502 (2019). https:\/\/doi.org\/10.1137\/19M125340X","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4_CR3","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1006\/jpdc.1996.0024","volume":"33","author":"SN Bhatt","year":"1996","unstructured":"Bhatt, S.N., Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Scheduling tree-dags using FIFO queues: A control-memory trade-off. J. Parallel Distrib. Comput. 33(1), 55\u201368 (1996). https:\/\/doi.org\/10.1006\/jpdc.1996.0024","journal-title":"J. Parallel Distrib. Comput."},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Bhore, S., Ganian, R., Montecchiani, F., N\u00f6llenburg, M.: Parameterized algorithms for queue layouts. CoRR abs\/2008.08288 (2020)","DOI":"10.1007\/978-3-030-68766-3_4"},{"key":"4_CR5","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00526","author":"S Bhore","year":"2020","unstructured":"Bhore, S., Ganian, R., Montecchiani, F., N\u00f6llenburg, M.: Parameterized algorithms for book embedding problems. J. Graph Algorithms Appl. (2020). https:\/\/doi.org\/10.7155\/jgaa.00526","journal-title":"J. Graph Algorithms Appl."},{"issue":"40\u201342","key":"4_CR6","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."},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/978-3-030-35802-0_35","volume-title":"Graph Drawing and Network Visualization","author":"P de Col","year":"2019","unstructured":"de Col, P., Klute, F., N\u00f6llenburg, M.: Mixed linear layouts: complexity, heuristics, and experiments. In: Archambault, D., T\u00f3th, C.D. (eds.) GD 2019. LNCS, vol. 11904, pp. 460\u2013467. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-35802-0_35"},{"key":"4_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"6","key":"4_CR9","doi-asserted-by":"publisher","first-page":"2243","DOI":"10.1137\/130908051","volume":"42","author":"G Di Battista","year":"2013","unstructured":"Di Battista, G., Frati, F., Pach, J.: On the queue number of planar graphs. SIAM J. Comput. 42(6), 2243\u20132285 (2013). https:\/\/doi.org\/10.1137\/130908051","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.comgeo.2004.11.003","volume":"32","author":"E Di Giacomo","year":"2005","unstructured":"Di Giacomo, E., Liotta, G., Meijer, H.: Computing straight-line 3d grid drawings of graphs in linear volume. Comput. Geom. 32(1), 26\u201358 (2005). https:\/\/doi.org\/10.1016\/j.comgeo.2004.11.003","journal-title":"Comput. Geom."},{"key":"4_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"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2014.07.005","volume":"110","author":"V Dujmovi\u0107","year":"2015","unstructured":"Dujmovi\u0107, V.: Graph layouts via layered separators. J. Comb. Theory, Ser. B 110, 79\u201389 (2015). https:\/\/doi.org\/10.1016\/j.jctb.2014.07.005","journal-title":"J. Comb. Theory, Ser. B"},{"key":"4_CR13","doi-asserted-by":"publisher","unstructured":"Dujmovi\u0107, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. In: Foundations of Computer Science (FOCS\u201919), pp. 862\u2013875. IEEE (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00056","DOI":"10.1109\/FOCS.2019.00056"},{"issue":"3","key":"4_CR14","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1137\/S0097539702416141","volume":"34","author":"V Dujmovi\u0107","year":"2005","unstructured":"Dujmovi\u0107, V., Morin, P., Wood, D.R.: Layout of graphs with bounded tree-width. SIAM J. Comput. 34(3), 553\u2013579 (2005). https:\/\/doi.org\/10.1137\/S0097539702416141","journal-title":"SIAM J. Comput."},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.jctb.2017.05.006","volume":"127","author":"V Dujmovi\u0107","year":"2017","unstructured":"Dujmovi\u0107, V., Morin, P., Wood, D.R.: Layered separators in minor-closed graph classes with applications. J. Comb. Theory, Ser. B 127, 111\u2013147 (2017). https:\/\/doi.org\/10.1016\/j.jctb.2017.05.006","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"4_CR16","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":"1","key":"4_CR17","first-page":"155","volume":"7","author":"V Dujmovi\u0107","year":"2005","unstructured":"Dujmovi\u0107, V., Wood, D.R.: Stacks, queues and tracks: layouts of graph subdivisions. Discrete Math. Theor. Comput. Sci. 7(1), 155\u2013202 (2005)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"4_CR18","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."},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Ganian, R., Peitl, T., Slivovsky, F., Szeider, S.: Fixed-parameter tractability of dependency QBF with structural parameters. In: Principles of Knowledge Representation and Reasoning (KR\u201920) (2020, to appear)","DOI":"10.24963\/kr.2020\/40"},{"issue":"4","key":"4_CR20","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":"4_CR21","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/0405031","volume":"5","author":"LS Heath","year":"1992","unstructured":"Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math. 5(3), 398\u2013412 (1992). https:\/\/doi.org\/10.1137\/0405031","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"4_CR22","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1137\/0221055","volume":"21","author":"LS Heath","year":"1992","unstructured":"Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21(5), 927\u2013958 (1992). https:\/\/doi.org\/10.1137\/0221055","journal-title":"SIAM J. Comput."},{"key":"4_CR23","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":"4_CR24","unstructured":"Ollmann, T.: On the book thicknesses of various graphs. In: Southeastern Conference on Combinatorics, Graph Theory and Computing. Congressus Numerantium, vol. VIII, p. 459 (1973)"},{"key":"4_CR25","unstructured":"Pemmaraju, S.V.: Exploring the powers of stacks and queues via graph layouts. Ph.D. thesis, Virginia Tech (1992)"},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-319-73915-1_17","volume-title":"Graph Drawing and Network Visualization","author":"S Pupyrev","year":"2018","unstructured":"Pupyrev, S.: Mixed linear layouts of planar graphs. In: Frati, F., Ma, K.-L. (eds.) GD 2017. LNCS, vol. 10692, pp. 197\u2013209. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73915-1_17"},{"key":"4_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"931","DOI":"10.1007\/978-3-662-43948-7_77","volume-title":"Automata, Languages, and Programming","author":"F Reidl","year":"2014","unstructured":"Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S.: A faster parameterized algorithm for treedepth. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part I. LNCS, vol. 8572, pp. 931\u2013942. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_77"},{"issue":"2","key":"4_CR28","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/321694.321704","volume":"19","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Sorting using networks of queues and stacks. J. ACM 19(2), 341\u2013346 (1972). https:\/\/doi.org\/10.1145\/321694.321704","journal-title":"J. ACM"},{"issue":"1","key":"4_CR29","doi-asserted-by":"publisher","first-page":"65","DOI":"10.37236\/6429","volume":"24","author":"V Wiechert","year":"2017","unstructured":"Wiechert, V.: On the queue-number of graphs with bounded tree-width. Electr. J. Comb. 24(1), 65 (2017). https:\/\/doi.org\/10.37236\/6429","journal-title":"Electr. J. Comb."},{"issue":"1","key":"4_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-68766-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T23:03:43Z","timestamp":1739401423000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-68766-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030687656","9783030687663"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-68766-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"14 February 2021","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":"Vancouver, BC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/gd2020.cs.ubc.ca\/","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":"82","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":"29","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":"9","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":"35% - 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,02","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":"3","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":"The conference was held virtually due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}