{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T18:34:01Z","timestamp":1792607641305,"version":"4.5.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We obtain new lower and upper bounds for the maximum multiplicity of some weighted and, respectively, nonweighted common geometric graphs drawn on $n$ points in the plane in general position (with no three points collinear): perfect matchings, spanning trees, spanning cycles (tours), and triangulations. (i) We present a new lower bound construction for the maximum number of triangulations a set of $n$ points in general position can have. In particular, we show that a generalized double chain formed by two almost convex chains admits $\\Omega (8.65^n)$ different triangulations. This improves the bound $\\Omega (8.48^n)$ achieved by the previous best construction, the double zig-zag chain studied by Aichholzer et al. (ii) We obtain a new lower bound of $\\Omega(12.00^n)$ for the number of noncrossing spanning trees of the double chain composed of two convex chains. The previous bound, $\\Omega(10.42^n)$, stood unchanged for more than 10 years. (iii) Using a recent upper bound of $30^n$ for the number of triangulations, due to Sharir and Sheffer, we show that $n$ points in the plane in general position admit at most $O(68.62^n)$ noncrossing spanning cycles. (iv) We derive lower bounds for the number of maximum and minimum weighted geometric graphs (matchings, spanning trees, and tours). We show that the number of shortest tours can be exponential in $n$ for points in general position. These tours are automatically noncrossing. Likewise, we show that the number of longest noncrossing tours can be exponential in $n$. It was known that the number of shortest noncrossing perfect matchings can be exponential in $n$, and here we show that the number of longest noncrossing perfect matchings can be also exponential in $n$. It was known that the number of longest noncrossing spanning trees of a point set can be exponentially large, and here we show that this can be also realized with points in convex position. For points in convex position we re-derive tight bounds for the number of longest and shortest tours with some simpler arguments. We also give a combinatorial characterization of longest tours, which yields an $O(n\\log n)$ time algorithm for computing them.<\/jats:p>","DOI":"10.1137\/110849407","type":"journal-article","created":{"date-parts":[[2013,4,18]],"date-time":"2013-04-18T11:09:58Z","timestamp":1366283398000},"page":"802-826","source":"Crossref","is-referenced-by-count":28,"title":["Bounds on the Maximum Multiplicity of Some Common Geometric Graphs"],"prefix":"10.1137","volume":"27","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andr\u00e9","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam","family":"Sheffer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,4,18]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-007-0704-5"},{"key":"atypb2","first-page":"9","volume":"12","author":"Ajtai M.","year":"1982","journal-title":"Ann. Discrete Math."},{"key":"atypb3","first-page":"385","volume":"22","author":"Alon N.","year":"1995","journal-title":"Fund. Inform."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876640"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"P. Beame, M. Saks, and J. Thathachar,<i>Time-space tradeoffs for branching programs<\/i> in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 254-263.","DOI":"10.1109\/SFCS.1998.743453"},{"key":"atypb6","first-page":"97","author":"Buchin K.","year":"2007","journal-title":"New York"},{"key":"atypb7","unstructured":"E. Demaine,<i>Simple Polygonizations<\/i> http:\/\/erikdemaine.org\/polygonization\/ (version of September 2012)."},{"key":"atypb8","unstructured":"A. Dumitrescu,<i>On two lower bound constructions<\/i> in Proceedings of the 11th Canadian Conference on Computational Geometry, 1999, pp. 111-114."},{"key":"atypb9","first-page":"5","volume":"12","author":"Dumitrescu A.","year":"2002","journal-title":"Geombinatorics"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00007-4"},{"key":"atypb11","first-page":"637","author":"Dumitrescu A.","year":"2011","journal-title":"Wadern"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00201-0"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-010-9277-9"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00372-0"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(00)00010-9"},{"key":"atypb16","first-page":"303","author":"Hoffmann M.","year":"2013","journal-title":"New York"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.05.006"},{"key":"atypb18","first-page":"169","volume":"45","author":"Hurtado F.","year":"1997","journal-title":"Ars Combin."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90041-6"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"J. Pach and P. K. Agarwal,<i>Combinatorial Geometry<\/i> John Wiley, New York, 1995.","DOI":"10.1002\/9781118033203"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0185508-8"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.039"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00002-5"},{"key":"atypb24","doi-asserted-by":"crossref","first-page":"70","DOI":"10.37236\/557","volume":"18","author":"Sharir M.","year":"2011","journal-title":"Electron. J. Combin."},{"key":"atypb25","unstructured":"M. Sharir and A. Sheffer,<i>Counting plane graphs: Cross-graph charging schemes<\/i> in Proceedings of the 20th Symposium on Graph Drawing, Lecture Notes in Comput. Sci. 7704, Springer, New York, to appear."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2013.01.002"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/050636036"},{"key":"atypb28","first-page":"273","author":"Sharir M.","year":"2006","journal-title":"New York"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1964-0163216-6"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110849407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:26:50Z","timestamp":1787318810000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110849407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/110849407"],"URL":"https:\/\/doi.org\/10.1137\/110849407","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}