{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:31:52Z","timestamp":1771036312093,"version":"3.50.1"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031231001","type":"print"},{"value":"9783031231018","type":"electronic"}],"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-23101-8_8","type":"book-chapter","created":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T20:18:53Z","timestamp":1671481133000},"page":"111-125","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parameterized Approaches to\u00a0Orthogonal Compaction"],"prefix":"10.1007","author":[{"given":"Walter","family":"Didimo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddharth","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5764-7719","authenticated-orcid":false,"given":"Philipp","family":"Kindermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5872-718X","authenticated-orcid":false,"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,1]]},"reference":[{"issue":"1","key":"8_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":"8_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":"3","key":"8_CR3","doi-asserted-by":"publisher","first-page":"651","DOI":"10.7155\/jgaa.00263","volume":"16","author":"MJ Bannister","year":"2012","unstructured":"Bannister, M.J., Eppstein, D., Simons, J.A.: Inapproximability of orthogonal compaction. J. Graph Algorithms Appl. 16(3), 651\u2013673 (2012). https:\/\/doi.org\/10.7155\/jgaa.00263","journal-title":"J. Graph Algorithms Appl."},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-319-03841-4_30","volume-title":"Graph Drawing","author":"MJ Bannister","year":"2013","unstructured":"Bannister, M.J., Eppstein, D., Simons, J.A.: Fixed parameter tractability of crossing minimization of almost-trees. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 340\u2013351. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03841-4_30"},{"key":"8_CR5","doi-asserted-by":"publisher","unstructured":"Bentley, J.L., Ottmann, T.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28(9), 643\u2013647 (1979). https:\/\/doi.org\/10.1109\/TC.1979.1675432","DOI":"10.1109\/TC.1979.1675432"},{"issue":"6","key":"8_CR6","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/BF01188716","volume":"12","author":"P Bertolazzi","year":"1994","unstructured":"Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476\u2013497 (1994). https:\/\/doi.org\/10.1007\/BF01188716","journal-title":"Algorithmica"},{"issue":"4","key":"8_CR7","doi-asserted-by":"publisher","first-page":"603","DOI":"10.7155\/jgaa.00526","volume":"24","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. 24(4), 603\u2013620 (2020). https:\/\/doi.org\/10.7155\/jgaa.00526","journal-title":"J. Graph Algorithms Appl."},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-030-68766-3_4","volume-title":"Graph Drawing and Network Visualization","author":"S Bhore","year":"2020","unstructured":"Bhore, S., Ganian, R., Montecchiani, F., N\u00f6llenburg, M.: Parameterized algorithms for queue layouts. In: GD 2020. LNCS, vol. 12590, pp. 40\u201354. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-68766-3_4"},{"issue":"1","key":"8_CR9","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s00454-010-9310-z","volume":"45","author":"T Biedl","year":"2010","unstructured":"Biedl, T.: Small drawings of outerplanar graphs, series-parallel graphs, and other planar graphs. Discrete Comput. Geom. 45(1), 141\u2013160 (2010). https:\/\/doi.org\/10.1007\/s00454-010-9310-z","journal-title":"Discrete Comput. Geom."},{"key":"8_CR10","doi-asserted-by":"publisher","unstructured":"Binucci, C., Da Lozzo, G., Di Giacomo, E., Didimo, W., Mchedlidze, T., Patrignani, M.: Upward book embeddings of st-graphs. In: Symposium on Computational Geometry (SoCG), vol. 129 of LIPIcs, pp. 1\u201322. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2019. https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2019.13","DOI":"10.4230\/LIPIcs.SoCG.2019.13"},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0925-7721(99)00054-1","volume":"16","author":"SS Bridgeman","year":"2000","unstructured":"Bridgeman, S.S., Di Battista, G., Didimo, W., Liotta, G., Tamassia, R., Vismara, L.: Turn-regularity and optimal area drawings of orthogonal representations. Comput. Geom. 16(1), 53\u201393 (2000). https:\/\/doi.org\/10.1016\/S0925-7721(99)00054-1","journal-title":"Comput. Geom."},{"key":"8_CR12","unstructured":"Chaplick, S., Di Giacomo, E., Frati, F., Ganian, R., Raftopoulou, C.N., Simonov, K.: Parameterized algorithms for upward planarity. arXiv (2022). https:\/\/doi.org\/10.48550\/arXiv.2203.05364"},{"key":"8_CR13","unstructured":"Chaplick, S., Fleszar, K., Lipp, F., Ravsky, A., Verbitsky, O., Wolff, A.: Drawing graphs on few lines and few planes. J. Comput. Geom. 11(1), 433\u2013475 (2020). https:\/\/doi.org\/10.20382\/jocg.v11i1a17"},{"key":"8_CR14","doi-asserted-by":"publisher","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"8_CR15","doi-asserted-by":"publisher","unstructured":"Da Lozzo, G., Eppstein, D., Goodrich, M.T., Gupta, S.: Subexponential-time and FPT algorithms for embedded flat clustered planarity. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 11159 of LNCS, pp. 111\u2013124. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-00256-5_10","DOI":"10.1007\/978-3-030-00256-5_10"},{"key":"8_CR16","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: algorithms for the Visualization of Graphs. Prentice-Hall (1999)"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(88)90123-5","volume":"61","author":"G Di Battista","year":"1988","unstructured":"Di Battista, G., Tamassia, R.: Algorithms for plane representations of acyclic digraphs. Theor. Comput. Sci. 61, 175\u2013198 (1988). https:\/\/doi.org\/10.1016\/0304-3975(88)90123-5","journal-title":"Theor. Comput. Sci."},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.jcss.2021.11.004","volume":"125","author":"E Di Giacomo","year":"2022","unstructured":"Di Giacomo, E., Liotta, G., Montecchiani, F.: Orthogonal planarity testing of bounded treewidth graphs. J. Comput. Syst. Sci. 125, 129\u2013148 (2022). https:\/\/doi.org\/10.1016\/j.jcss.2021.11.004","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Didimo, W., Gupta, S., Kindermann, P., Liotta, G., Wolff, A., Zehavi, M.: Parameterized approaches to orthogonal compaction. arXiv (2022). https:\/\/doi.org\/10.48550\/arXiv.2210.05019","DOI":"10.1007\/978-3-031-23101-8_8"},{"key":"8_CR20","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity, vol. 4 of TCS. Springer (2013).https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"8_CR21","doi-asserted-by":"publisher","unstructured":"Dujmovi\u0107, V., et al.: On the parameterized complexity of layered graph drawing. Algorithmica 52(2), 267\u2013292 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9151-1","DOI":"10.1007\/s00453-007-9151-1"},{"issue":"2","key":"8_CR22","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.jda.2006.12.008","volume":"6","author":"V Dujmovi\u0107","year":"2008","unstructured":"Dujmovi\u0107, V., Fernau, H., Kaufmann, M.: Fixed parameter algorithms for one-sided crossing minimization revisited. J. Discrete Algorithms 6(2), 313\u2013323 (2008). https:\/\/doi.org\/10.1016\/j.jda.2006.12.008","journal-title":"J. Discrete Algorithms"},{"issue":"101820","key":"8_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comgeo.2021.101820","volume":"100","author":"WS Evans","year":"2022","unstructured":"Evans, W.S., Fleszar, K., Kindermann, P., Saeedi, N., Shin, C.-S., Wolff, A.: Minimum rectilinear polygons for given angle sequences. Comput. Geom. 100(101820), 1\u201339 (2022). https:\/\/doi.org\/10.1016\/j.comgeo.2021.101820","journal-title":"Comput. Geom."},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press (2019)","DOI":"10.1017\/9781107415157"},{"issue":"6","key":"8_CR25","doi-asserted-by":"publisher","first-page":"82","DOI":"10.4230\/DagRep.11.6.82","volume":"11","author":"R Ganian","year":"2021","unstructured":"Ganian, R., Montecchiani, F., N\u00f6llenburg, M., Zehavi, M.: Parameterized complexity in graph drawing (Dagstuhl Seminar 21293). Dagstuhl Rep. 11(6), 82\u2013123 (2021). https:\/\/doi.org\/10.4230\/DagRep.11.6.82","journal-title":"Dagstuhl Rep."},{"key":"8_CR26","doi-asserted-by":"publisher","unstructured":"Gupta, S., Sa\u2019ar, G., Zehavi, M.: Grid recognition: classical and parameterized computational perspectives. In: International Symposium on Algorithms and Computation (ISAAC), vol. 212 of LIPIcs, pp. 1\u201315. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2021.37","DOI":"10.4230\/LIPIcs.ISAAC.2021.37"},{"key":"8_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44969-8","volume-title":"Drawing Graphs","year":"2001","unstructured":"Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44969-8"},{"key":"8_CR28","doi-asserted-by":"publisher","unstructured":"Kobayashi, Y., Ohtsuka, H., Tamaki, H.: An improved fixed-parameter algorithm for one-page crossing minimization. In: Lokshtanov, D., Nishimura, N. (eds.) 12th International Symposium on Parameterized and Exact Computation (IPEC), vol. 89 of LIPIcs, pp. 1\u201312. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.25","DOI":"10.4230\/LIPIcs.IPEC.2017.25"},{"key":"8_CR29","doi-asserted-by":"publisher","unstructured":"Liotta, G., Rutter, I., Tappini, A.: Parameterized complexity of graph planarity with restricted cyclic orders. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), vol. 13453 of LNCS, pp. 383\u2013397. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_28","DOI":"10.1007\/978-3-031-15914-5_28"},{"issue":"8","key":"8_CR30","doi-asserted-by":"publisher","first-page":"2471","DOI":"10.1007\/s00453-021-00839-2","volume":"83","author":"G Da Lozzo","year":"2021","unstructured":"Da Lozzo, G., Eppstein, D., Goodrich, M.T., Gupta, S.: C-planarity testing of embedded clustered graphs with bounded dual carving-width. Algorithmica 83(8), 2471\u20132502 (2021). https:\/\/doi.org\/10.1007\/s00453-021-00839-2","journal-title":"Algorithmica"},{"issue":"1","key":"8_CR31","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0925-7721(01)00010-4","volume":"19","author":"M Patrignani","year":"2001","unstructured":"Patrignani, M.: On the complexity of orthogonal compaction. Comput. Geom. 19(1), 47\u201367 (2001). https:\/\/doi.org\/10.1016\/S0925-7721(01)00010-4","journal-title":"Comput. Geom."},{"key":"8_CR32","unstructured":"Pickover, C.A.: The Math Book. Sterling (2009)"},{"key":"8_CR33","doi-asserted-by":"publisher","unstructured":"Shamos, M.I., Hoey, D.: Geometric intersection problems. In: 17th Annual Symposium on Foundations of Computer Science (FOCS), pp. 208\u2013215 (1976). https:\/\/doi.org\/10.1109\/SFCS.1976.16","DOI":"10.1109\/SFCS.1976.16"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2023: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-23101-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T00:05:30Z","timestamp":1673049930000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-23101-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031231001","9783031231018"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-23101-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"1 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nov\u00fd Smokovec","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","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":"15 January 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 January 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ics.science.upjs.sk\/sofsem2023\/","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":"43","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":"26","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":"0","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":"60% - 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":"6-7","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)"}}]}}