{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T16:22:34Z","timestamp":1747153354489,"version":"3.40.5"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031492747"},{"type":"electronic","value":"9783031492754"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-49275-4_13","type":"book-chapter","created":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T12:02:46Z","timestamp":1704715366000},"page":"189-202","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parameterized and\u00a0Approximation Algorithms for\u00a0the\u00a0Maximum Bimodal Subgraph Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4379-6059","authenticated-orcid":false,"given":"Walter","family":"Didimo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0184-5932","authenticated-orcid":false,"given":"Tanmay","family":"Inamdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0477-2724","authenticated-orcid":false,"given":"Stephen","family":"Kobourov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7491-2811","authenticated-orcid":false,"given":"Marie Diana","family":"Sieper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,1,6]]},"reference":[{"issue":"3","key":"13_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.7155\/jgaa.00596","volume":"26","author":"P Angelini","year":"2022","unstructured":"Angelini, P., Chaplick, S., Cornelsen, S., Da Lozzo, G.: Planar L-drawings of bimodal graphs. J. Graph Algorithms Appl. 26(3), 307\u2013334 (2022). https:\/\/doi.org\/10.7155\/jgaa.00596","journal-title":"J. Graph Algorithms Appl."},{"key":"13_CR2","doi-asserted-by":"publisher","unstructured":"Angelini, P., Chaplick, S., Cornelsen, S., Lozzo, G.D.: On upward-planar L-drawings of graphs. In: Szeider, S., Ganian, R., Silva, A. (eds.) 47th International Symposium on Mathematical Foundations of Computer Science. MFCS 2022, 22\u201326 August 2022, Vienna, Austria. LIPIcs, vol. 241, pp. 10:1\u201310:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2022.10","DOI":"10.4230\/LIPIcs.MFCS.2022.10"},{"issue":"4","key":"13_CR3","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1142\/S0129054118410010","volume":"29","author":"P Angelini","year":"2018","unstructured":"Angelini, P., et al.: Algorithms and bounds for L-drawings of directed graphs. Int. J. Found. Comput. Sci. 29(4), 461\u2013480 (2018). https:\/\/doi.org\/10.1142\/S0129054118410010","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"13_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach. 41(1), 153\u2013180 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"13_CR5","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/s00453-001-0083-x","volume":"32","author":"P Bertolazzi","year":"2002","unstructured":"Bertolazzi, P., Di Battista, G., Didimo, W.: Quasi-upward planarity. Algorithmica 32(3), 474\u2013506 (2002). https:\/\/doi.org\/10.1007\/s00453-001-0083-x","journal-title":"Algorithmica"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-030-92931-2_14","volume-title":"Graph Drawing and Network Visualization","author":"C Binucci","year":"2021","unstructured":"Binucci, C., Di Giacomo, E., Liotta, G., Tappini, A.: Quasi-upward planar drawings with\u00a0minimum curve complexity. In: Purchase, H.C., Rutter, I. (eds.) GD 2021. LNCS, vol. 12868, pp. 195\u2013209. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-92931-2_14"},{"issue":"1","key":"13_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/comjnl\/bxv082","volume":"59","author":"C Binucci","year":"2016","unstructured":"Binucci, C., Didimo, W.: Computing quasi-upward planar drawings of mixed graphs. Comput. J. 59(1), 133\u2013150 (2016). https:\/\/doi.org\/10.1093\/comjnl\/bxv082","journal-title":"Comput. J."},{"issue":"3","key":"13_CR8","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/j.comgeo.2008.02.001","volume":"41","author":"C Binucci","year":"2008","unstructured":"Binucci, C., Didimo, W., Giordano, F.: Maximum upward planar subgraphs of embedded planar digraphs. Comput. Geom. 41(3), 230\u2013246 (2008). https:\/\/doi.org\/10.1016\/j.comgeo.2008.02.001","journal-title":"Comput. Geom."},{"issue":"1\u20132","key":"13_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theor. Comput. Sci."},{"key":"13_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-319-73915-1_36","volume-title":"Graph Drawing and Network Visualization","author":"S Chaplick","year":"2018","unstructured":"Chaplick, S., et al.: Planar L-drawings of directed graphs. In: Frati, F., Ma, K.-L. (eds.) GD 2017. LNCS, vol. 10692, pp. 465\u2013478. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73915-1_36"},{"key":"13_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","journal-title":"Parameterized Algorithms"},{"key":"13_CR12","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River (1999)"},{"issue":"6","key":"13_CR13","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1109\/21.23105","volume":"18","author":"G Di Battista","year":"1988","unstructured":"Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Syst. Man Cybern. 18(6), 1035\u20131046 (1988). https:\/\/doi.org\/10.1109\/21.23105","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"13_CR14","doi-asserted-by":"publisher","unstructured":"Didimo, W.: Upward graph drawing. In: Encyclopedia of Algorithms, pp. 2308\u20132312 (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_653","DOI":"10.1007\/978-1-4939-2864-4_653"},{"key":"13_CR15","doi-asserted-by":"publisher","unstructured":"Didimo, W., Fomin, F.V., Golovach, P.A., Inamdar, T., Kobourov, S., Sieper, M.D.: Parameterized and approximation algorithms for the maximum bimodal subgraph problem (2023). https:\/\/doi.org\/10.48550\/arXiv.2308.15635","DOI":"10.48550\/arXiv.2308.15635"},{"issue":"3","key":"13_CR16","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1007\/s00453-009-9296-1","volume":"58","author":"F Dorn","year":"2010","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790\u2013810 (2010). https:\/\/doi.org\/10.1007\/s00453-009-9296-1","journal-title":"Algorithmica"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2016.06.004","volume":"84","author":"M Etscheid","year":"2017","unstructured":"Etscheid, M., Kratsch, S., Mnich, M., R\u00f6glin, H.: Polynomial kernels for weighted problems. J. Comput. Syst. Sci. 84, 1\u201310 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2016.06.004","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR18","volume-title":"Kernelization. Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization. Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"issue":"1","key":"13_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1002\/jgt.20121","volume":"51","author":"FV Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: New upper bounds on the decomposability of planar graphs. J. Graph Theory 51(1), 53\u201381 (2006). https:\/\/doi.org\/10.1002\/jgt.20121","journal-title":"J. Graph Theory"},{"key":"13_CR20","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF02579200","volume":"7","author":"A Frank","year":"1987","unstructured":"Frank, A., Tardos, \u00c9.: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7, 49\u201365 (1987). https:\/\/doi.org\/10.1007\/BF02579200","journal-title":"Combinatorica"},{"key":"13_CR21","doi-asserted-by":"publisher","unstructured":"Impagliazzo, R., Paturi, R.: Complexity of k-sat. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, 4\u20136 May 1999, pp. 237\u2013240. IEEE Computer Society (1999). https:\/\/doi.org\/10.1109\/CCC.1999.766282","DOI":"10.1109\/CCC.1999.766282"},{"issue":"4","key":"13_CR22","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-031-15914-5_21","volume-title":"Graph-Theoretic Concepts in Computer Science - WG 2022","author":"H Jacob","year":"2022","unstructured":"Jacob, H., Pilipczuk, M.: Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. In: Bekos, M.A., Kaufmann, M. (eds.) WG 2022. LNCS, vol. 13453, pp. 287\u2013299. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_21"},{"key":"13_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/3-540-37623-2_17","volume-title":"Graph Drawing","author":"M J\u00fcnger","year":"1998","unstructured":"J\u00fcnger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 224\u2013237. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-37623-2_17"},{"key":"13_CR25","doi-asserted-by":"publisher","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. x. obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52(2), 153\u2013190 (1991). https:\/\/doi.org\/10.1016\/0095-8956(91)90061-N","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"13_CR26","doi-asserted-by":"publisher","unstructured":"Vial, J.J.B., Da Lozzo, G., Goodrich, M.T.: Computing $$k$$-modal embeddings of planar digraphs. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, 9\u201311 September 2019, Munich\/Garching, Germany. LIPIcs, vol. 144, pp. 19:1\u201319:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.19","DOI":"10.4230\/LIPIcs.ESA.2019.19"}],"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-031-49275-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,8]],"date-time":"2024-01-08T12:04:09Z","timestamp":1704715449000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49275-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031492747","9783031492754"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49275-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"6 January 2024","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":"Isola delle Femmine, Palermo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"gd2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/gd2023.ing.unipg.it\/\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-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":"100","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":"31","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":"7","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":"31% - 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","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":"13","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":"11 posters, 2 abstracts of invited talks, and 1 contest report are also included in the GD 2023 proceedings","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)"}}]}}