{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T11:47:33Z","timestamp":1747136853496,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031555978"},{"type":"electronic","value":"9783031555985"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-55598-5_1","type":"book-chapter","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T18:01:53Z","timestamp":1709661713000},"page":"3-18","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On 1-Bend Upward Point-Set Embeddings of\u00a0st-Digraphs"],"prefix":"10.1007","author":[{"given":"Emilio","family":"Di Giacomo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry","family":"F\u00f6rster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daria","family":"Kokhovich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamara","family":"Mchedlidze","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Montecchiani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonios","family":"Symvonis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ana\u00efs","family":"Villedieu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,6]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-18469-7_3","volume-title":"GD 2010","author":"P Angelini","year":"2010","unstructured":"Angelini, P., Frati, F., Geyer, M., Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward geometric graph embeddings into point sets. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 25\u201337. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-18469-7_3"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/978-3-030-68211-8_19","volume-title":"WALCOM 2021","author":"E Arseneva","year":"2021","unstructured":"Arseneva, E., et al.: Upward point set embeddings of paths and trees. In: Uehara, R., Hong, S.H., Nandy, S.C. (eds.) WALCOM 2021. LNCS, vol. 12635, pp. 234\u2013246. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-68211-8_19"},{"issue":"2\u20133","key":"1_CR3","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.tcs.2008.08.004","volume":"408","author":"M Badent","year":"2008","unstructured":"Badent, M., Di Giacomo, E., Liotta, G.: Drawing colored graphs on colored points. Theor. Comput. Sci. 408(2\u20133), 129\u2013142 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113689","volume":"946","author":"MA Bekos","year":"2023","unstructured":"Bekos, M.A., Da Lozzo, G., Frati, F., Gronemann, M., Mchedlidze, T., Raftopoulou, C.N.: Recognizing DAGs with page-number 2 is NP-complete. Theor. Comput. Sci. 946, 113689 (2023)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1_CR5","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)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2022.103662","volume":"110","author":"S Bhore","year":"2023","unstructured":"Bhore, S., Da Lozzo, G., Montecchiani, F., N\u00f6llenburg, M.: On the upward book thickness problem: combinatorial and complexity results. Eur. J. Comb. 110, 103662 (2023)","journal-title":"Eur. J. Comb."},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.comgeo.2009.07.002","volume":"43","author":"C Binucci","year":"2010","unstructured":"Binucci, C., et al.: Upward straight-line embeddings of directed graphs into point sets. Comput. Geom. 43(2), 219\u2013232 (2010)","journal-title":"Comput. Geom."},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0925-7721(01)00069-4","volume":"23","author":"P Bose","year":"2002","unstructured":"Bose, P.: On embedding an outer-planar graph on a point set. Comput. Geom. Theory Appl. 23, 303\u2013312 (2002)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"1_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00002","volume":"2","author":"P Bose","year":"1997","unstructured":"Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. J. Graph Algorithms Appl. 2(1), 1\u201315 (1997)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"1_CR10","doi-asserted-by":"publisher","first-page":"353","DOI":"10.7155\/jgaa.00132","volume":"10","author":"S Cabello","year":"2006","unstructured":"Cabello, S.: Planar embeddability of the vertices of a graph using a fixed point set is NP-hard. J. Graph Algorithms Appl. 10(2), 353\u2013363 (2006)","journal-title":"J. Graph Algorithms Appl."},{"issue":"6\u20137","key":"1_CR11","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1016\/j.comgeo.2009.01.001","volume":"42","author":"E Di Giacomo","year":"2009","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Point-set embeddings of trees with given partial drawings. Comput. Geom. 42(6\u20137), 664\u2013676 (2009)","journal-title":"Comput. Geom."},{"issue":"4","key":"1_CR12","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00453-005-1185-7","volume":"45","author":"E Di Giacomo","year":"2006","unstructured":"Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Book embeddability of series-parallel digraphs. Algorithmica 45(4), 531\u2013547 (2006). https:\/\/doi.org\/10.1007\/s00453-005-1185-7","journal-title":"Algorithmica"},{"key":"1_CR13","unstructured":"Di Giacomo, E., et al.: On 1-bend upward point-set embeddings of $$st$$-digraphs. CoRR 2401.03226 (2024). http:\/\/arxiv.org\/2401.03226"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.tcs.2020.09.027","volume":"846","author":"E Di Giacomo","year":"2020","unstructured":"Di Giacomo, E., Gasieniec, L., Liotta, G., Navarra, A.: On the curve complexity of 3-colored point-set embeddings. Theor. Comput. Sci. 846, 114\u2013140 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"1_CR15","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1007\/s00453-008-9255-2","volume":"57","author":"E Di Giacomo","year":"2010","unstructured":"Di Giacomo, E., Liotta, G., Trotta, F.: Drawing colored graphs with constrained vertex positions and few bends per edge. Algorithmica 57(4), 796\u2013818 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9255-2","journal-title":"Algorithmica"},{"issue":"1","key":"1_CR16","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.comgeo.2012.03.003","volume":"46","author":"V Dujmovi\u0107","year":"2013","unstructured":"Dujmovi\u0107, V., et al.: On point-sets that support planar graphs. Comput. Geom. 46(1), 29\u201350 (2013)","journal-title":"Comput. Geom."},{"issue":"2","key":"1_CR17","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/s00454-009-9149-3","volume":"43","author":"H Everett","year":"2010","unstructured":"Everett, H., Lazard, S., Liotta, G., Wismath, S.K.: Universal sets of $$n$$ points for one-bend drawings of planar graphs with $$n$$ vertices. Discrete Comput. Geom. 43(2), 272\u2013288 (2010). https:\/\/doi.org\/10.1007\/s00454-009-9149-3","journal-title":"Discrete Comput. Geom."},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.jda.2014.11.006","volume":"30","author":"F Giordano","year":"2015","unstructured":"Giordano, F., Liotta, G., Mchedlidze, T., Symvonis, A., Whitesides, S.: Computing upward topological book embeddings of upward planar digraphs. J. Discrete Algorithms 30, 45\u201369 (2015)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"1_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.2307\/2323956","volume":"98","author":"P Gritzmann","year":"1991","unstructured":"Gritzmann, P., Mohar, B., Pach, J., Pollack, R.: Embedding a planar triangulation with vertices at specified points. Am. Math. Monthly 98(2), 165\u2013166 (1991)","journal-title":"Am. Math. Monthly"},{"issue":"5","key":"1_CR20","doi-asserted-by":"publisher","first-page":"1588","DOI":"10.1137\/S0097539795291550","volume":"28","author":"LS Heath","year":"1999","unstructured":"Heath, L.S., Pemmaraju, S.V.: Stack and queue layouts of directed acyclic graphs: part II. SIAM J. Comput. 28(5), 1588\u20131626 (1999)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1_CR21","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1016\/j.comgeo.2012.11.008","volume":"46","author":"M Kaufmann","year":"2013","unstructured":"Kaufmann, M., Mchedlidze, T., Symvonis, A.: On upward point set embeddability. Comput. Geom. 46(6), 774\u2013804 (2013)","journal-title":"Comput. Geom."},{"issue":"1","key":"1_CR22","doi-asserted-by":"publisher","first-page":"115","DOI":"10.7155\/jgaa.00046","volume":"6","author":"M Kaufmann","year":"2002","unstructured":"Kaufmann, M., Wiese, R.: Embedding vertices at points: few bends suffice for planar graphs. J. Graph Algorithms Appl. 6(1), 115\u2013129 (2002)","journal-title":"J. Graph Algorithms Appl."},{"key":"1_CR23","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-319-27261-0_35","volume-title":"GD 2015","author":"M L\u00f6ffler","year":"2015","unstructured":"L\u00f6ffler, M., T\u00f3th, C.D.: Linear-size universal point sets for one-bend drawings. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 423\u2013429. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-27261-0_35"},{"issue":"8","key":"1_CR24","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1016\/j.comgeo.2013.05.004","volume":"46","author":"T Mchedlidze","year":"2013","unstructured":"Mchedlidze, T.: Upward planar embedding of an n-vertex oriented path on $$O(n^2)$$ points. Comput. Geom. 46(8), 1003\u20131008 (2013)","journal-title":"Comput. Geom."},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1007\/978-3-642-10631-6_89","volume-title":"ISAAC 2009","author":"T Mchedlidze","year":"2009","unstructured":"Mchedlidze, T., Symvonis, A.: Crossing-free acyclic hamiltonian path completion for planar $$st$$-digraphs. In: Dong, Y., Du, D.Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 882\u2013891. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_89"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-00202-1_22","volume-title":"WALCOM 2009","author":"T Mchedlidze","year":"2009","unstructured":"Mchedlidze, T., Symvonis, A.: Crossing-optimal acyclic hamiltonian path completion and its application to upward topological book embeddings. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol. 5431, pp. 250\u2013261. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00202-1_22"},{"issue":"4","key":"1_CR27","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/PL00007258","volume":"17","author":"J Pach","year":"2001","unstructured":"Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs Comb. 17(4), 717\u2013728 (2001). https:\/\/doi.org\/10.1007\/PL00007258","journal-title":"Graphs Comb."}],"container-title":["Lecture Notes in Computer Science","LATIN 2024: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-55598-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T18:01:58Z","timestamp":1709661718000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-55598-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031555978","9783031555985"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-55598-5_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"6 March 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Varas","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Chile","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 March 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 March 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/latin2024.cmm.uchile.cl\/","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":"92","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":"44","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":"48% - 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.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":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}