{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T07:06:13Z","timestamp":1770966373354,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T00:00:00Z","timestamp":1768953600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T00:00:00Z","timestamp":1768953600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100019945","name":"Direcci\u00f3 General de Recerca, Generalitat de Catalunya","doi-asserted-by":"publisher","award":["2021-SGR-00266"],"award-info":[{"award-number":["2021-SGR-00266"]}],"id":[{"id":"10.13039\/501100019945","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["PID2023-150725NB-I00"],"award-info":[{"award-number":["PID2023-150725NB-I00"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In 1962, Tutte provided a formula for the number of combinatorial triangulations, that is, maximal planar graphs with a fixed triangular face and\n                    <jats:italic>n<\/jats:italic>\n                    additional vertices. In this note, we study in how many ways a combinatorial triangulation can be drawn as geometric triangulation, that is, with straight-line segments, on a given point set in the plane. Our central contribution is that there exist a combinatorial triangulation\n                    <jats:italic>T<\/jats:italic>\n                    and a point set\n                    <jats:italic>S<\/jats:italic>\n                    such that\n                    <jats:italic>T<\/jats:italic>\n                    can be drawn on\n                    <jats:italic>S<\/jats:italic>\n                    in at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\varOmega (1,31^n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03a9<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:msup>\n                              <mml:mn>31<\/mml:mn>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    ways as different geometric triangulations. We also show an upper bound on the number of drawings of a combinatorial triangulation on the so-called double chain point set.\n                  <\/jats:p>","DOI":"10.1007\/s00373-026-03010-2","type":"journal-article","created":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T08:01:45Z","timestamp":1768982505000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Number of Drawings of a Combinatorial Triangulation"],"prefix":"10.1007","volume":"42","author":[{"given":"Bel\u00e9n","family":"Cruces","sequence":"first","affiliation":[]},{"given":"Clemens","family":"Huemer","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2253-7098","authenticated-orcid":false,"given":"Dolores","family":"Lara","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,21]]},"reference":[{"key":"3010_CR1","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s00373-007-0704-5","volume":"23","author":"O Aichholzer","year":"2007","unstructured":"Aichholzer, O., Hackl, T., Huemer, C., Hurtado, F., Krasser, H., Vogtenhuber, B.: On the number of plane geometric graphs. Graphs Comb. 23, 67\u201384 (2007)","journal-title":"Graphs Comb."},{"issue":"2","key":"3010_CR2","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.jcta.2007.06.002","volume":"115","author":"O Aichholzer","year":"2008","unstructured":"Aichholzer, O., Orden, D., Santos, F., Speckmann, B.: On the number of pseudo-triangulations of certain point sets. J. Comb. Theory Ser. A 115(2), 254\u2013278 (2008)","journal-title":"J. Comb. Theory Ser. A"},{"key":"3010_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M.M., Szemer\u00e9di, E.: Crossing-free subgraphs, In Theory and Practice of Combinatorics, volume 60 of North-Holland Mathematics Studies, pp. 9\u201312. North-Holland (1982)","DOI":"10.1016\/S0304-0208(08)73484-4"},{"key":"3010_CR4","unstructured":"Cruces Mateo, B.: On the number of drawings of a combinatorial triangulation, Master thesis. Universitat Polit\u00e8cnica de Catalunya (2023), URL: http:\/\/hdl.handle.net\/2117\/396459"},{"key":"3010_CR5","unstructured":"Denny, M., Sohler, C.: Encoding a triangulation as a permutation of its point set. In: Proceedings of the 9th Canadian Conference on Computational Geometry, pp. 39\u201343 (1997)"},{"issue":"2","key":"3010_CR6","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1137\/110849407","volume":"27","author":"A Dumitrescu","year":"2013","unstructured":"Dumitrescu, A., Schulz, A., Sheffer, A., T\u00f3th, C.D.: Bounds on the maximum multiplicity of some common geometric graphs. SIAM J. Discret. Math. 27(2), 802\u2013826 (2013)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"3010_CR7","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0925-7721(00)00010-9","volume":"16","author":"A Garc\u00eda","year":"2000","unstructured":"Garc\u00eda, A., Noy, M., Tejel, J.: Lower bounds on the number of crossing-free subgraphs of $$K_N$$. Comput. Geom. 16(4), 211\u2013221 (2000)","journal-title":"Comput. Geom."},{"key":"3010_CR8","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.ejc.2015.02.008","volume":"48","author":"C Huemer","year":"2015","unstructured":"Huemer, C., de Mier, A.: Lower bounds on the maximum number of non-crossing acyclic graphs. Eur. J. Comb. 48, 48\u201362 (2015)","journal-title":"Eur. J. Comb."},{"issue":"3","key":"3010_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3585535","volume":"70","author":"D Rutschmann","year":"2023","unstructured":"Rutschmann, D., Wettstein, M.: Chains, Koch chains, and point sets with many triangulations. J. ACM 70(3), 1\u201326 (2023)","journal-title":"J. ACM"},{"issue":"1","key":"3010_CR10","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/S0097-3165(03)00002-5","volume":"102","author":"F Santos","year":"2003","unstructured":"Santos, F., Seidel, R.: A better upper bound on the number of triangulations of a planar point set. J. Comb. Theory Ser. A 102(1), 186\u2013193 (2003)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"2","key":"3010_CR11","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/PL00009823","volume":"18","author":"R Seidel","year":"1998","unstructured":"Seidel, R.: On the number of triangulations of planar point sets. Combinatorica 18(2), 297\u2013299 (1998)","journal-title":"Combinatorica"},{"issue":"1","key":"3010_CR12","doi-asserted-by":"publisher","first-page":"P70","DOI":"10.37236\/557","volume":"18","author":"M Sharir","year":"2011","unstructured":"Sharir, M., Sheffer, A.: Counting triangulations of planar point sets. Electron. J. Comb. 18(1), P70 (2011)","journal-title":"Electron. J. Comb."},{"key":"3010_CR13","doi-asserted-by":"crossref","unstructured":"Sharir, M., Welzl, E.: Random triangulations of planar point sets, Proceedings of the 22nd Annual Symposium on Computational Geometry, 273\u2013281 (2006)","DOI":"10.1145\/1137856.1137898"},{"key":"3010_CR14","unstructured":"Smith, W.D.: Studies in Computational Geometry Motivated by Mesh Generation. Ph.D. Dissertation. Princeton University (1989)"},{"key":"3010_CR15","unstructured":"Tejel, J.: personal communication (2025)"},{"key":"3010_CR16","doi-asserted-by":"publisher","first-page":"21","DOI":"10.4153\/CJM-1962-002-9","volume":"14","author":"WT Tutte","year":"1962","unstructured":"Tutte, W.T.: A census of planar triangulations. Can. J. Math. 14, 21\u201338 (1962)","journal-title":"Can. J. Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-026-03010-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-026-03010-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-026-03010-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:05:46Z","timestamp":1770962746000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-026-03010-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,21]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["3010"],"URL":"https:\/\/doi.org\/10.1007\/s00373-026-03010-2","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,21]]},"assertion":[{"value":"24 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2026","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"16"}}