{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:15:00Z","timestamp":1747196100164,"version":"3.40.5"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T00:00:00Z","timestamp":1741996800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T00:00:00Z","timestamp":1741996800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78"],"award-info":[{"award-number":["PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78","PRIN 2022ME9Z78"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100008991","name":"Universit\u00e0 degli Studi Roma Tre","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008991","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,6]]},"abstract":"Abstract<\/jats:title>\n We study upward pointset embeddings (UPSE<\/jats:sc>s) of planar st<\/jats:italic>-graphs. Let G<\/jats:italic> be a planar st<\/jats:italic>-graph and let \n \n $$S \\subset \\mathbb {R}^2$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u2282<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> be a pointset with \n \n $$|S|= |V(G)|$$<\/jats:tex-math>\n \n \n |<\/mml:mo>\n S<\/mml:mi>\n |<\/mml:mo>\n =<\/mml:mo>\n |<\/mml:mo>\n V<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. An UPSE<\/jats:italic> of G<\/jats:italic> on S<\/jats:italic> is an upward planar straight-line drawing of G<\/jats:italic> that maps the vertices of G<\/jats:italic> to the points of S<\/jats:italic>. We consider both the problem of testing the existence of an UPSE<\/jats:sc> of G<\/jats:italic> on S<\/jats:italic> (UPSE Testing<\/jats:sc>) and the problem of enumerating all UPSE<\/jats:sc>s of G<\/jats:italic> on S<\/jats:italic>. We prove that UPSE Testing<\/jats:sc> is -complete even for st<\/jats:italic>-graphs that consist of a set of directed st<\/jats:italic>-paths sharing only s<\/jats:italic> and t<\/jats:italic>. On the other hand, if G<\/jats:italic> is an n<\/jats:italic>-vertex planar st<\/jats:italic>-graph whose maximum st<\/jats:italic>-cutset has size k<\/jats:italic>, then UPSE Testing<\/jats:sc> can be solved in \n \n $$\\mathcal {O}(n^{4k})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 4<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> time with \n \n $$\\mathcal {O}(n^{3k})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> space; also, all the UPSE<\/jats:sc>s of G<\/jats:italic> on S<\/jats:italic> can be enumerated with \n \n $$\\mathcal {O}(n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> worst-case delay, using \n \n $$\\mathcal {O}(k n^{4k} \\log n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n \n n<\/mml:mi>\n \n 4<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> space, after \n \n $$\\mathcal {O}(k n^{4k} \\log n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n k<\/mml:mi>\n \n n<\/mml:mi>\n \n 4<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> set-up time. Moreover, for an n<\/jats:italic>-vertex st<\/jats:italic>-graph whose underlying graph is a cycle, we provide a necessary and sufficient condition for the existence of an UPSE<\/jats:sc> on a given pointset, which can be tested in \n \n $$\\mathcal {O}(n \\log n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> time. Related to this result, we give an algorithm that, for a set S<\/jats:italic> of n<\/jats:italic> points, enumerates all the non-crossing monotone Hamiltonian cycles on S<\/jats:italic> with \n \n $$\\mathcal {O}(n)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> worst-case delay, using \n \n $$\\mathcal {O}(n^2)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> space, after \n \n $$\\mathcal {O}(n^2)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> set-up time.<\/jats:p>","DOI":"10.1007\/s00453-025-01302-2","type":"journal-article","created":{"date-parts":[[2025,3,15]],"date-time":"2025-03-15T19:38:46Z","timestamp":1742067526000},"page":"930-960","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Upward Pointset Embeddings of Planar st-Graphs"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5512-5298","authenticated-orcid":false,"given":"Carlos","family":"Alegr\u00ed\u00ada","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0001-4538-8198","authenticated-orcid":false,"given":"Susanna","family":"Caroppo","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-5174","authenticated-orcid":false,"given":"Giordano","family":"Da Lozzo","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0008-6266-3324","authenticated-orcid":false,"given":"Marco","family":"D\u2019Elia","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4224-1550","authenticated-orcid":false,"given":"Giuseppe","family":"Di Battista","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5987-8713","authenticated-orcid":false,"given":"Fabrizio","family":"Frati","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5766-4567","authenticated-orcid":false,"given":"Fabrizio","family":"Grosso","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9806-7411","authenticated-orcid":false,"given":"Maurizio","family":"Patrignani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,15]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Alegr\u00eda, C., Caroppo, S., Da Lozzo, G., D\u2019Elia, M., Di Battista, G., Frati, F., Grosso, F., Patrignani, M.: Upward pointset embeddings of planar st-graphs. In: Felsner, S., Klein, K. (eds.) 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). LIPIcs, vol.\u00a0320, pp. 24:1\u201324:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.GD.2024.24","key":"1302_CR1","DOI":"10.4230\/LIPICS.GD.2024.24"},{"issue":"4","key":"1302_CR2","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/S00454-015-9672-3","volume":"53","author":"V Alvarez","year":"2015","unstructured":"Alvarez, V., Bringmann, K., Curticapean, R., Ray, S.: Counting triangulations and other crossing-free structures via onion layers. Discret. Comput. Geom. 53(4), 675\u2013690 (2015). https:\/\/doi.org\/10.1007\/S00454-015-9672-3","journal-title":"Discret. Comput. Geom."},{"doi-asserted-by":"publisher","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.) 18th International Symposium on Graph Drawing (GD 2010). LNCS, vol.\u00a06502, pp. 25\u201337. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-18469-7_3","key":"1302_CR3","DOI":"10.1007\/978-3-642-18469-7_3"},{"doi-asserted-by":"publisher","unstructured":"Arseneva, E., Cano, P., Kleist, L., Mchedlidze, T., Mehrabi, S., Parada, I., Valtr, P.: Upward point set embeddings of paths and trees. In: Uehara, R., Hong, S., Nandy, S.C. (eds.) 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021). LNCS, vol. 12635, pp. 234\u2013246. Springer (2021).https:\/\/doi.org\/10.1007\/978-3-030-68211-8_19","key":"1302_CR4","DOI":"10.1007\/978-3-030-68211-8_19"},{"doi-asserted-by":"publisher","unstructured":"Biedl, T., Vatshelle, M.: The point-set embeddability problem for plane graphs. In: Dey, T.K., Whitesides, S. (eds.) 28th ACM Symposium on Computational Geometry (SoCG 2012). pp. 41\u201350. ACM (2012).https:\/\/doi.org\/10.1145\/2261250.2261257,","key":"1302_CR5","DOI":"10.1145\/2261250.2261257"},{"issue":"2","key":"1302_CR6","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., Di Giacomo, E., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S.G., Liotta, G.: Upward straight-line embeddings of directed graphs into point sets. Comput. Geom. 43(2), 219\u2013232 (2010). https:\/\/doi.org\/10.1016\/J.COMGEO.2009.07.002","journal-title":"Comput. Geom."},{"doi-asserted-by":"publisher","unstructured":"Bose, P.: On embedding an outer-planar graph in a point set. In: Di Battista, G. (ed.) 5th International Symposium on Graph Drawing (GD \u201997). LNCS, vol.\u00a01353, pp. 25\u201336. Springer (1997). https:\/\/doi.org\/10.1007\/3-540-63938-1_47","key":"1302_CR7","DOI":"10.1007\/3-540-63938-1_47"},{"issue":"3","key":"1302_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 in a point set. Comput. Geom. 23(3), 303\u2013312 (2002). https:\/\/doi.org\/10.1016\/S0925-7721(01)00069-4","journal-title":"Comput. Geom."},{"doi-asserted-by":"publisher","unstructured":"Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. In: Brandenburg, F. (ed.) Symposium on Graph Drawing (GD \u201995). LNCS, vol.\u00a01027, pp. 64\u201375. Springer (1995). https:\/\/doi.org\/10.1007\/BFB0021791","key":"1302_CR9","DOI":"10.1007\/BFB0021791"},{"issue":"2","key":"1302_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/JGAA.00002","volume":"1","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. 1(2), 1\u201315 (1997). https:\/\/doi.org\/10.7155\/JGAA.00002","journal-title":"J. Graph Algorithms Appl."},{"issue":"2","key":"1302_CR11","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). https:\/\/doi.org\/10.7155\/JGAA.00132","journal-title":"J. Graph Algorithms Appl."},{"doi-asserted-by":"crossref","unstructured":"Casta\u00f1eda, N., Urrutia, J.: Straight line embeddings of planar graphs on point sets. In: Fiala, F., Kranakis, E., Sack, J. (eds.) 8th Canadian Conference on Computational Geometry (CCCG 1996). pp. 312\u2013318. Carleton University Press (1996), http:\/\/www.cccg.ca\/proceedings\/1996\/cccg1996_0052.pdf","key":"1302_CR12","DOI":"10.1515\/9780773591134-055"},{"key":"1302_CR13","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/J.DAM.2022.04.008","volume":"317","author":"G Cheon","year":"2022","unstructured":"Cheon, G., Choi, H.J., Esteban, G., Song, M.: Enumeration of bipartite non-crossing geometric graphs. Discret. Appl. Math. 317, 86\u2013100 (2022). https:\/\/doi.org\/10.1016\/J.DAM.2022.04.008","journal-title":"Discret. Appl. Math."},{"unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 4th edn. MIT Press, (2022) https:\/\/mitpress.mit.edu\/9780262046305\/introduction-to-algorithms\/","key":"1302_CR14"},{"doi-asserted-by":"publisher","unstructured":"Da Lozzo, G., Di Battista, G., Frati, F., Grosso, F., Patrignani, M.: Efficient enumeration of drawings and combinatorial structures for maximal planar graphs. In: Uehara, R., Yamanaka, K., Yen, H. (eds.) 18th International Conference and Workshops on Algorithms and Computation (WALCOM 2024). LNCS, vol. 14549, pp. 350\u2013364. Springer (2024). https:\/\/doi.org\/10.1007\/978-981-97-0566-5_25","key":"1302_CR15","DOI":"10.1007\/978-981-97-0566-5_25"},{"doi-asserted-by":"publisher","unstructured":"Di Battista, G., Didimo, W., Grilli, L., Grosso, F., Ortali, G., Patrignani, M., Tappini, A.: Small point-sets supporting graph stories. In: Angelini, P., von Hanxleden, R. (eds.) 30th International Symposium on Graph Drawing and Network Visualization (GD 2022). LNCS, vol. 13764, pp. 289\u2013303. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-22203-0_21","key":"1302_CR16","DOI":"10.1007\/978-3-031-22203-0_21"},{"unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999)","key":"1302_CR17"},{"key":"1302_CR18","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."},{"doi-asserted-by":"publisher","unstructured":"Di Giacomo, E., F\u00f6rster, H., Kokhovich, D., Mchedlidze, T., Montecchiani, F., Symvonis, A., Villedieu, A.: On 1-bend upward point-set embeddings of st-digraphs. In: Soto, J.A., Wiese, A. (eds.) 16th Latin American Symposium on Theoretical Informatics (LATIN 2024), Part I. LNCS, vol. 14578, pp. 3\u201318. Springer (2024). https:\/\/doi.org\/10.1007\/978-3-031-55598-5_1","key":"1302_CR19","DOI":"10.1007\/978-3-031-55598-5_1"},{"doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edn., Graduate texts in mathematics, vol.\u00a0173. Springer (2012)","key":"1302_CR20","DOI":"10.1007\/978-3-662-53622-3_7"},{"issue":"4","key":"1302_CR21","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1007\/S00454-020-00251-7","volume":"64","author":"D Eppstein","year":"2020","unstructured":"Eppstein, D.: Counting polygon triangulations is hard. Discret. Comput. Geom. 64(4), 1210\u20131234 (2020). https:\/\/doi.org\/10.1007\/S00454-020-00251-7","journal-title":"Discret. Comput. Geom."},{"issue":"9","key":"1302_CR22","doi-asserted-by":"publisher","first-page":"3027","DOI":"10.1007\/S00453-024-01255-Y","volume":"86","author":"D Eppstein","year":"2024","unstructured":"Eppstein, D.: Non-crossing hamiltonian paths and cycles in output-polynomial time. Algorithmica 86(9), 3027\u20133053 (2024). https:\/\/doi.org\/10.1007\/S00453-024-01255-Y","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"1302_CR23","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0012-365X(98)00372-0","volume":"204","author":"P Flajolet","year":"1999","unstructured":"Flajolet, P., Noy, M.: Analytic combinatorics of non-crossing configurations. Discret. Math. 204(1\u20133), 203\u2013229 (1999). https:\/\/doi.org\/10.1016\/S0012-365X(98)00372-0","journal-title":"Discret. Math."},{"unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. 1st edn. W. H. Freeman (1979)","key":"1302_CR24"},{"key":"1302_CR25","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). https:\/\/doi.org\/10.1016\/J.JDA.2014.11.006","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"1302_CR26","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. Mon. 98(2), 165 (1991). https:\/\/doi.org\/10.2307\/2323956","journal-title":"Am. Math. Mon."},{"issue":"4","key":"1302_CR27","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/S0097539795280287","volume":"28","author":"LS Heath","year":"1999","unstructured":"Heath, L.S., Pemmaraju, S.V., Trenk, A.N.: Stack and queue layouts of directed acyclic graphs: Part I. SIAM J. Comput. 28(4), 1510\u20131539 (1999). https:\/\/doi.org\/10.1137\/S0097539795280287","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"publisher","unstructured":"Kaufmann, M., Mchedlidze, T., Symvonis, A.: Upward point set embeddability for convex point sets is in P. In: van Kreveld, M.J., Speckmann, B. (eds.) 19th International Symposium on Graph Drawing (GD 2011). LNCS, vol.\u00a07034, pp. 403\u2013414. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-25878-7_38","key":"1302_CR28","DOI":"10.1007\/978-3-642-25878-7_38"},{"issue":"6","key":"1302_CR29","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). https:\/\/doi.org\/10.1016\/J.COMGEO.2012.11.008","journal-title":"Comput. Geom."},{"doi-asserted-by":"publisher","unstructured":"Kaufmann, M., Wiese, R.: Embedding vertices at points: Few bends suffice for planar graphs. In: Kratochv\u00edl, J. (ed.) 7th International Symposium on Graph Drawing (GD\u201999). LNCS, vol.\u00a01731, pp. 165\u2013174. Springer (1999). https:\/\/doi.org\/10.1007\/3-540-46648-7_17","key":"1302_CR30","DOI":"10.1007\/3-540-46648-7_17"},{"issue":"1","key":"1302_CR31","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). https:\/\/doi.org\/10.7155\/JGAA.00046","journal-title":"J. Graph Algorithms Appl."},{"doi-asserted-by":"publisher","unstructured":"Marx, D., Miltzow, T.: Peeling and nibbling the cactus: Subexponential-time algorithms for counting triangulations and related problems. In: Fekete, S.P., Lubiw, A. (eds.) 32nd International Symposium on Computational Geometry (SoCG 2016). LIPIcs, vol.\u00a051, pp. 52:1\u201352:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016). https:\/\/doi.org\/10.4230\/LIPICS.SOCG.2016.52","key":"1302_CR32","DOI":"10.4230\/LIPICS.SOCG.2016.52"},{"issue":"8","key":"1302_CR33","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$$ ^{\\text{2 }}$$) points. Comput. Geom. 46(8), 1003\u20131008 (2013). https:\/\/doi.org\/10.1016\/J.COMGEO.2013.05.004","journal-title":"Comput. Geom."},{"issue":"5","key":"1302_CR34","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1142\/S0218195901000651","volume":"11","author":"JSB Mitchell","year":"2001","unstructured":"Mitchell, J.S.B., O\u2019Rourke, J.: Computational geometry column 42. Int. J. Comput. Geom. Appl. 11(5), 573\u2013582 (2001). https:\/\/doi.org\/10.1142\/S0218195901000651","journal-title":"Int. J. Comput. Geom. Appl."},{"doi-asserted-by":"publisher","unstructured":"Nishat, R.I., Mondal, D., Rahman, M.S.: Point-set embeddings of plane 3-trees - (extended abstract). In: Brandes, U., Cornelsen, S. (eds.) 18th International Symposium on Graph Drawing (GD 2010). LNCS, vol.\u00a06502, pp. 317\u2013328. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-18469-7_29","key":"1302_CR35","DOI":"10.1007\/978-3-642-18469-7_29"},{"issue":"3","key":"1302_CR36","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/J.COMGEO.2011.09.002","volume":"45","author":"RI Nishat","year":"2012","unstructured":"Nishat, R.I., Mondal, D., Rahman, M.S.: Point-set embeddings of plane 3-trees. Comput. Geom. 45(3), 88\u201398 (2012). https:\/\/doi.org\/10.1016\/J.COMGEO.2011.09.002","journal-title":"Comput. Geom."},{"doi-asserted-by":"publisher","unstructured":"Razen, A., Welzl, E.: Counting plane graphs with exponential speed-up. In: Calude, C.S., Rozenberg, G., Salomaa, A. (eds.) Rainbow of Computer Science - Dedicated to Hermann Maurer on the Occasion of His 70th Birthday. LNCS, vol.\u00a06570, pp. 36\u201346. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-19391-0_3","key":"1302_CR37","DOI":"10.1007\/978-3-642-19391-0_3"},{"doi-asserted-by":"publisher","unstructured":"Shamos, M.I., Hoey, D.: Geometric intersection problems. In: 17th Annual Symposium on Foundations of Computer Science (FOCS 1976). pp. 208\u2013215. IEEE Computer Society (1976).https:\/\/doi.org\/10.1109\/SFCS.1976.16","key":"1302_CR38","DOI":"10.1109\/SFCS.1976.16"},{"issue":"1","key":"1302_CR39","doi-asserted-by":"publisher","first-page":"47","DOI":"10.20382\/JOCG.V8I1A4","volume":"8","author":"M Wettstein","year":"2017","unstructured":"Wettstein, M.: Counting and enumerating crossing-free geometric graphs. J. Comput. Geom. 8(1), 47\u201377 (2017). https:\/\/doi.org\/10.20382\/JOCG.V8I1A4","journal-title":"J. Comput. Geom."},{"key":"1302_CR40","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/J.DAM.2020.03.034","volume":"303","author":"K Yamanaka","year":"2021","unstructured":"Yamanaka, K., Avis, D., Horiyama, T., Okamoto, Y., Uehara, R., Yamauchi, T.: Algorithmic enumeration of surrounding polygons. Discret. Appl. Math. 303, 305\u2013313 (2021). https:\/\/doi.org\/10.1016\/J.DAM.2020.03.034","journal-title":"Discret. Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01302-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01302-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01302-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T11:23:28Z","timestamp":1747135408000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01302-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,15]]},"references-count":40,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["1302"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01302-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,3,15]]},"assertion":[{"value":"13 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}