{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T11:45:34Z","timestamp":1747136734819},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,3,17]],"date-time":"2015-03-17T00:00:00Z","timestamp":1426550400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s00454-015-9672-3","type":"journal-article","created":{"date-parts":[[2015,3,16]],"date-time":"2015-03-16T14:37:34Z","timestamp":1426516654000},"page":"675-690","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Counting Triangulations and Other Crossing-Free Structures via Onion Layers"],"prefix":"10.1007","volume":"53","author":[{"given":"Victor","family":"Alvarez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karl","family":"Bringmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Radu","family":"Curticapean","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saurabh","family":"Ray","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,3,17]]},"reference":[{"key":"9672_CR1","doi-asserted-by":"crossref","unstructured":"Aichholzer, O.: The path of a triangulation. In: Proceedings of the 15th Annual Symposium on Computational Geometry, SoCG \u201999, pp. 14\u201323. ACM Press, New York (1999)","DOI":"10.1145\/304893.304896"},{"key":"9672_CR2","unstructured":"Aichholzer, O., Krasser, H.: The point set order type data base: a collection of applications and results. In: Proceedings of the 13th Canadian Conference on Computational Geometry, CCCG \u201901, pp. 17\u201320. Waterloo (2001)"},{"issue":"2","key":"9672_CR3","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/j.comgeo.2004.02.003","volume":"29","author":"O Aichholzer","year":"2004","unstructured":"Aichholzer, O., Hurtado, F., Noy, M.: A lower bound on the number of triangulations of planar point sets. Comput. Geom. 29(2), 135\u2013145 (2004)","journal-title":"Comput. Geom."},{"issue":"5","key":"9672_CR4","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s00373-007-0750-z","volume":"23","author":"O Aichholzer","year":"2007","unstructured":"Aichholzer, O., Aurenhammer, F., Huemer, C., Vogtenhuber, B.: Gray code enumeration of plane straight-line graphs. Graphs Comb. 23(5), 467\u2013479 (2007)","journal-title":"Graphs Comb."},{"issue":"1","key":"9672_CR5","doi-asserted-by":"crossref","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(1), 67\u201384 (2007)","journal-title":"Graphs Comb."},{"key":"9672_CR6","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. In: Peter, G.S., Hammer, L., Rosa, A., Turgeon, J. (eds.) Theory and Practice of Combinatorics a Collection of Articles Honoring Anton Kotzig on the Occasion of His Sixtieth Birthday. North-Holland Mathematics Studies, vol. 60, pp. 9\u201312. North-Holland, Amsterdam (1982)","DOI":"10.1016\/S0304-0208(08)73484-4"},{"key":"9672_CR7","doi-asserted-by":"crossref","unstructured":"Alvarez, V., Seidel, R.: A simple aggregative algorithm for counting triangulations of planar point sets and related problems. In: Proceedings of the 29th Annual Symposium on Computational Geometry, SoCG \u201913, pp. 1\u20138. ACM Press, New York (2013)","DOI":"10.1145\/2462356.2462392"},{"key":"9672_CR8","doi-asserted-by":"crossref","unstructured":"Alvarez, V., Bringmann, K., Curticapean, R., Ray, S.: Counting crossing-free structures. In: Proceedings of the 28th Annual Symposium on Computational Geometry, SoCG \u201912, pp. 61\u201368. ACM Press, New York (2012)","DOI":"10.1145\/2261250.2261259"},{"key":"9672_CR9","unstructured":"Alvarez, V., Bringmann, K., Curticapean, R., Ray, S.: Counting triangulations and other crossing-free structures via onion layers. Computing Research Repository (CoRR) (2013). Available at http:\/\/arxiv.org\/abs\/1312.4628"},{"key":"9672_CR10","unstructured":"Alvarez, V., Bringmann, K., Ray, S.: A simple sweep line algorithm for counting triangulations and pseudo-triangulations. Computing Research Repository (CoRR) (2013). Available at http:\/\/arxiv.org\/abs\/1312.3188"},{"issue":"5","key":"9672_CR11","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1016\/j.comgeo.2014.12.006","volume":"48","author":"V Alvarez","year":"2015","unstructured":"Alvarez, V., Bringmann, K., Ray, S., Seidel, R.: Counting triangulations and other crossing-free structures approximately. Comput. Geom. 48(5), 386\u2013397 (2015)","journal-title":"Comput. Geom."},{"issue":"5","key":"9672_CR12","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0925-7721(93)90016-Y","volume":"3","author":"E Anagnostou","year":"1993","unstructured":"Anagnostou, E., Corneil, D.: Polynomial-time instances of the minimum weight triangulation problem. Comput. Geom. 3(5), 247\u2013259 (1993)","journal-title":"Comput. Geom."},{"key":"9672_CR13","doi-asserted-by":"crossref","unstructured":"Auer, T., Held, M.: Heuristics for the generation of random polygons. In: Proceedings of the 8th Canadian Conference on Computational Geometry, CCCG \u201996, pp. 38\u201343. (1996)","DOI":"10.1515\/9780773591134-009"},{"issue":"1\u20133","key":"9672_CR14","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D Avis","year":"1996","unstructured":"Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1\u20133), 21\u201346 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9672_CR15","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/S0925-7721(02)00111-6","volume":"23","author":"S Bespamyatnikh","year":"2002","unstructured":"Bespamyatnikh, S.: An efficient algorithm for enumeration of triangulations. Comput. Geom. 23(3), 271\u2013279 (2002)","journal-title":"Comput. Geom."},{"issue":"1\u20134","key":"9672_CR16","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01553881","volume":"4","author":"LP Chew","year":"1989","unstructured":"Chew, L.P.: Constrained Delaunay triangulations. Algorithmica 4(1\u20134), 97\u2013108 (1989)","journal-title":"Algorithmica"},{"issue":"2","key":"9672_CR17","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1002\/rsa.10114","volume":"24","author":"K Dalal","year":"2004","unstructured":"Dalal, K.: Counting the onion. Random Struct. Algorithms 24(2), 155\u2013165 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"9672_CR18","unstructured":"Demaine, E., Mitchell, J.S.B., O\u2019Rourke, J.: Problem 16: Simple Polygonalizations. http:\/\/cs.smith.edu\/~orourke\/TOPP\/P16.html#Problem.16 (2014). Accessed 12 May 2014"},{"issue":"2","key":"9672_CR19","doi-asserted-by":"crossref","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. Discrete Math. 27(2), 802\u2013826 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20133","key":"9672_CR20","doi-asserted-by":"crossref","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. Discrete Math. 204(1\u20133), 203\u2013229 (1999). Selected papers in honor of Henry W. Gould","journal-title":"Discrete Math."},{"key":"9672_CR21","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"issue":"4","key":"9672_CR22","doi-asserted-by":"crossref","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$$ K n . Comput. Geom. 16(4), 211\u2013221 (2000)","journal-title":"Comput. Geom."},{"key":"9672_CR23","volume-title":"Triangulations and Applications (Mathematics and Visualization)","author":"\u00d8 Hjelle","year":"2006","unstructured":"Hjelle, \u00d8., D\u00e6hlen, M.: Triangulations and Applications (Mathematics and Visualization). Springer, Berlin (2006)"},{"key":"9672_CR24","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/978-1-4614-0110-0_16","volume-title":"Thirty Essays on Geometric Graph Theory","author":"M Hoffmann","year":"2013","unstructured":"Hoffmann, M., Schulz, A., Sharir, M., Sheffer, A., T\u00f3th, C., Welzl, E.: Counting plane graphs: flippability and its applications. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 303\u2013325. Springer, New York (2013)"},{"key":"9672_CR25","unstructured":"Huemer, C., de Mier, A.: Lower bounds on the maximum number of non-crossing acyclic graphs. arXiv preprint 1310.5882, (2013). Available http:\/\/arxiv.org\/abs\/1310.5882"},{"issue":"3","key":"9672_CR26","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/s00454-009-9164-4","volume":"42","author":"N Katoh","year":"2009","unstructured":"Katoh, N., Tanigawa, S.: Fast enumeration algorithms for non-crossing geometric graphs. Discrete Comput. Geom. 42(3), 443\u2013468 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"9672_CR27","unstructured":"Ray, S., Seidel, R.: A simple and less slow method for counting triangulations and for related problems. In: Proceedings of the 20th European Workshop on Computational Geometry, EWCG \u201904 (2004)"},{"key":"9672_CR28","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/978-3-642-19391-0_3","volume-title":"Rainbow of Computer Science, vol. 6570","author":"A Razen","year":"2011","unstructured":"Razen, A., Welzl, E.: Counting plane graphs with exponential speed-up. In: Calude, C., Rozenberg, G., Salomaa, A. (eds.) Rainbow of Computer Science, vol. 6570, pp. 36\u201346. Springer, Heidelberg (2011)"},{"issue":"1","key":"9672_CR29","doi-asserted-by":"crossref","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":"3","key":"9672_CR30","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1137\/050636036","volume":"36","author":"M Sharir","year":"2006","unstructured":"Sharir, M., Welzl, E.: On the number of crossing-free matchings, cycles, and partitions. SIAM J. Comput. 36(3), 695\u2013720 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9672_CR31","doi-asserted-by":"crossref","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."},{"issue":"7","key":"9672_CR32","doi-asserted-by":"crossref","first-page":"1979","DOI":"10.1016\/j.jcta.2011.04.002","volume":"118","author":"M Sharir","year":"2011","unstructured":"Sharir, M., Sheffer, A., Welzl, E.: On degrees in random triangulations of point sets. J. Comb. Theory Ser. A 118(7), 1979\u20131999 (2011)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"4","key":"9672_CR33","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1016\/j.jcta.2013.01.002","volume":"120","author":"M Sharir","year":"2013","unstructured":"Sharir, M., Sheffer, A., Welzl, E.: Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn\u2019s technique. J. Comb. Theory Ser. A 120(4), 777\u2013794 (2013)","journal-title":"J. Comb. Theory Ser. A"},{"key":"9672_CR34","unstructured":"Sheffer, A.: Numbers of plane graphs. http:\/\/www.cs.tau.ac.il\/~sheffera\/counting\/PlaneGraphs.html (2014). Accessed May 12 2014"},{"key":"9672_CR35","doi-asserted-by":"crossref","unstructured":"Wettstein, M.: Counting and enumerating crossing-free geometric graphs. In: Proceedings of the 30th annual Symposium on Computational Geometry, SoCG \u201914, pp. 1\u201310. ACM Press, New York (2014)","DOI":"10.1145\/2582112.2582145"},{"issue":"5","key":"9672_CR36","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0925-7721(95)00031-3","volume":"6","author":"C Zhu","year":"1996","unstructured":"Zhu, C., Sundaram, G., Snoeyink, J., Mitchell, J.S.: Generating random polygons with given vertices. Comput. Geom. 6(5), 277\u2013290 (1996)","journal-title":"Comput. Geom."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9672-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9672-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9672-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T20:44:14Z","timestamp":1691527454000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9672-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,17]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["9672"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9672-3","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,17]]}}}