{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T07:53:21Z","timestamp":1725436401134},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,4,22]],"date-time":"2009-04-22T00:00:00Z","timestamp":1240358400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00454-009-9164-4","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T14:57:53Z","timestamp":1240325873000},"page":"443-468","source":"Crossref","is-referenced-by-count":9,"title":["Fast Enumeration Algorithms for Non-crossing Geometric Graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"Naoki","family":"Katoh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shin-Ichi","family":"Tanigawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,22]]},"reference":[{"issue":"1","key":"9164_CR1","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.ipl.2005.09.003","volume":"97","author":"O. Aichholzer","year":"2006","unstructured":"Aichholzer, O., Aurenhammer, F., Huemer, C., Krasser, H.: Transforming spanning trees and pseudo-triangulations. Inf. Process. Lett. 97(1), 19\u201322 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"9164_CR2","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\u20132","key":"9164_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(01)00042-6","volume":"21","author":"O. Aichholzer","year":"2002","unstructured":"Aichholzer, O., Aurenhammer, F., Hurtado, F.: Sequences of spanning trees and a fixed tree theorem. Comput. Geom. 21(1\u20132), 3\u201320 (2002)","journal-title":"Comput. Geom."},{"issue":"1","key":"9164_CR4","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":"9164_CR5","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/j.comgeo.2004.12.010","volume":"37","author":"O. Aichholzer","year":"2007","unstructured":"Aichholzer, O., Reinhardt, K.: A quadratic distance bound on sliding between crossing-free spanning trees. Comput. Geom. Theory Appl. 37, 155\u2013161 (2007)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9164_CR6","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF02293050","volume":"8","author":"D. Avis","year":"1992","unstructured":"Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom. 8, 295\u2013313 (1992)","journal-title":"Discrete Comput. Geom."},{"issue":"1\u20133","key":"9164_CR7","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":"1","key":"9164_CR8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s00373-007-0709-0","volume":"23","author":"D. Avis","year":"2007","unstructured":"Avis, D., Katoh, N., Ohsaki, M., Streinu, I., Tanigawa, S.: Enumerating non-crossing minimally rigid frameworks. Graphs Comb. 23(1), 117\u2013134 (2007)","journal-title":"Graphs Comb."},{"issue":"1","key":"9164_CR9","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00454-007-9026-x","volume":"40","author":"D. Avis","year":"2008","unstructured":"Avis, D., Katoh, N., Ohsaki, M., Streinu, I., Tanigawa, S.: Enumerating constrained non-crossing minimally rigid frameworks. Discrete Comput. Geom. 40(1), 31\u201346 (2008)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9164_CR10","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.comgeo.2004.09.002","volume":"30","author":"S. Bereg","year":"2005","unstructured":"Bereg, S.: Enumerating pseudo-triangulations in the plane. Comput. Geom. Theory Appl. 30(3), 207\u2013222 (2005)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9164_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/978-3-540-39658-1_10","volume-title":"Proc. 11th Annual European Symposium on Algorithms (ESA)","author":"A. Berg","year":"2003","unstructured":"Berg, A., Jord\u00e1n, T.: Algorithms for graph rigidity and scene analysis. In: Proc. 11th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2832, pp. 78\u201389. Springer, Berlin (2003)"},{"issue":"3","key":"9164_CR12","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. Theory Appl. 23(3), 271\u2013279 (2002)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"9164_CR13","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/050631008","volume":"36","author":"H. Br\u00f6nnimann","year":"2006","unstructured":"Br\u00f6nnimann, H., Kettner, L., Pocchiola, M., Snoeyink, J.: Counting and enumerating pointed pseudo-triangulations with the greedy flip algorithm. SIAM J. Comput. 36(3), 721\u2013739 (2006)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9164_CR14","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B. Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6(5), 485\u2013524 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"9164_CR15","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"9164_CR16","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, 203\u2013229 (1999)","journal-title":"Discrete Math."},{"key":"9164_CR17","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/002","volume-title":"Combinatorial Rigidity","author":"J. Graver","year":"1993","unstructured":"Graver, J., Servatius, B., Servatius, H.: Combinatorial Rigidity, Graduate Studies in Mathematics, vol.\u00a02. American Mathematical Society, Reading (1993)"},{"key":"9164_CR18","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L.J. Guibas","year":"1987","unstructured":"Guibas, L.J., Hershberger, J., Leven, D., Sharir, M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2, 209\u2013233 (1987)","journal-title":"Algorithmica"},{"issue":"2","key":"9164_CR19","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1137\/S009753979225030X","volume":"24","author":"S. Kapoor","year":"1995","unstructured":"Kapoor, S., Ramesh, H.: Algorithms for enumerating all spanning trees of undirected and weighted graphs. SIAM J. Comput. 24(2), 247\u2013265 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9164_CR20","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/s004530010008","volume":"27","author":"S. Kapoor","year":"2000","unstructured":"Kapoor, S., Ramesh, H.: An algorithm for enumerating all spanning trees of a directed graph. Algorithmica 27(2), 120\u2013130 (2000)","journal-title":"Algorithmica"},{"key":"9164_CR21","unstructured":"Katoh, N., Tanigawa, S.: Enumerating edge-constrained triangulations and edge-constrained non-crossing spanning trees. Discrete Appl. Math. (to appear)"},{"key":"9164_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/3-540-44968-X_6","volume-title":"Proc. 6th International Conference Computing and Combinatorics, COCOON 2000","author":"M.C. Hernando","year":"2000","unstructured":"Hernando, M.C., Houle, M.E., Hurtado, F.: On local transformation of polygons with visibility properties. In: Proc. 6th International Conference Computing and Combinatorics, COCOON 2000. Lecture Notes in Computer Science, vol. 1858, pp. 54\u201363. Springer, Berlin (2000)"},{"issue":"3","key":"9164_CR23","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/s003730200038","volume":"18","author":"C. Hernando","year":"2002","unstructured":"Hernando, C., Hurtado, F., Noy, M.: Graphs of non-crossing perfect matchings. Graphs Comb. 18(3), 517\u2013532 (2002)","journal-title":"Graphs Comb."},{"issue":"3","key":"9164_CR24","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/s00373-005-0615-2","volume":"21","author":"M.E. Houle","year":"2005","unstructured":"Houle, M.E., Hurtado, F., Noy, M., Rivera-Campo, E.: Graphs of triangulations and perfect matchings. Graphs Comb. 21(3), 325\u2013331 (2005)","journal-title":"Graphs Comb."},{"issue":"3","key":"9164_CR25","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/PL00009464","volume":"22","author":"F. Hurtado","year":"1999","unstructured":"Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete Comput. Geom. 22(3), 333\u2013346 (1999)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9164_CR26","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1007\/BF01990536","volume":"33","author":"K. Jansen","year":"1993","unstructured":"Jansen, K., Woeginger, G.J.: The complexity of detecting crossingfree configurations in the plane. BIT 33(4), 580\u2013595 (1993)","journal-title":"BIT"},{"issue":"8","key":"9164_CR27","doi-asserted-by":"crossref","first-page":"1425","DOI":"10.1016\/j.disc.2007.07.104","volume":"308","author":"A. Lee","year":"2008","unstructured":"Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Discrete Math. 308(8), 1425\u20131437 (2008)","journal-title":"Discrete Math."},{"key":"9164_CR28","unstructured":"Matsui, Y., Matsui, T., Fukuda, K.: A catalog of enumeration algorithms. http:\/\/roso.epfl.ch\/kf\/enum\/enum.html"},{"key":"9164_CR29","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/S0036144595295272","volume":"39","author":"C. Savage","year":"1997","unstructured":"Savage, C.: A survey of combinatorial Gray codes. SIAM Rev. 39, 605\u2013629 (1997)","journal-title":"SIAM Rev."},{"key":"9164_CR30","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"issue":"3","key":"9164_CR31","first-page":"331","volume":"38","author":"A. Shioura","year":"1995","unstructured":"Shioura, A., Tamura, A.: Efficiently scanning all spanning trees of an undirected graph. J. Oper. Res. Soc. J. 38(3), 331\u2013344 (1995)","journal-title":"J. Oper. Res. Soc. J."},{"issue":"3","key":"9164_CR32","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1137\/S0097539794270881","volume":"26","author":"A. Shioura","year":"1997","unstructured":"Shioura, A., Tamura, A., Uno, T.: An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM J. Comput. 26(3), 678\u2013692 (1997)","journal-title":"SIAM J. Comput."},{"key":"9164_CR33","series-title":"Lecture Notes in Computer Science","first-page":"54","volume-title":"Proc. 5th Computing and Combinatorics Conference (COCOON \u201999)","author":"T. Uno","year":"1999","unstructured":"Uno, T.: A new approach for speeding up enumeration algorithms and its application for matroid bases. In: Proc. 5th Computing and Combinatorics Conference (COCOON \u201999). Lecture Notes in Computer Science, vol. 1627, pp. 54\u201363. Springer, Berlin (1999)"},{"key":"9164_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/3-540-49381-6_31","volume-title":"Proc. 9th International Symposium on Algorithm and Computation (ISAAC \u201998)","author":"T. Uno","year":"1998","unstructured":"Uno, T.: A new approach for speeding up enumeration algorithms. In: Proc. 9th International Symposium on Algorithm and Computation (ISAAC \u201998). Lecture Notes in Computer Science, vol. 1533, pp. 287\u2013296. Springer, Berlin (1998)"},{"key":"9164_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1007\/3-540-63890-3_11","volume-title":"Proc. 8th International Symposium on Algorithms and Computation (ISAAC \u201997)","author":"T. Uno","year":"1997","unstructured":"Uno, T.: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In: Proc. 8th International Symposium on Algorithms and Computation (ISAAC \u201997). Lecture Notes in Computer Science, vol. 1350, pp. 92\u2013101. Springer, Berlin (1997)"},{"key":"9164_CR36","unstructured":"Welzl, E.: Counting of crossing-free geometric graphs. In: Significant Advances in Computer Science (SACS 07), Graz, Austria, November 2007"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9164-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9164-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9164-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:37Z","timestamp":1559087257000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9164-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,22]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9164"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9164-4","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,22]]}}}