{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:35Z","timestamp":1740109595513,"version":"3.37.3"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T00:00:00Z","timestamp":1680825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T00:00:00Z","timestamp":1680825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s00454-023-00487-z","type":"journal-article","created":{"date-parts":[[2023,4,7]],"date-time":"2023-04-07T15:02:31Z","timestamp":1680879751000},"page":"728-742","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Dirac\u2013Goodman\u2013Pollack Conjecture"],"prefix":"10.1007","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1118-0321","authenticated-orcid":false,"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,7]]},"reference":[{"key":"487_CR1","doi-asserted-by":"crossref","unstructured":"Ackerman, E.: On topological graphs with at most four crossings per edge. Comput. Geom. 85, #\u00a0101574 (2019)","DOI":"10.1016\/j.comgeo.2019.101574"},{"key":"487_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44205-0","volume-title":"Proofs from THE BOOK","author":"M Aigner","year":"2014","unstructured":"Aigner, M., Ziegler, G.M.: Proofs from THE BOOK. Springer, Berlin (2014)"},{"key":"487_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. North-Holland Math. Stud., vol. 60. Ann. Discrete Math., vol. 12, pp. 9\u201312. North-Holland, Amsterdam (1982)","DOI":"10.1016\/S0304-0208(08)73484-4"},{"issue":"3","key":"487_CR4","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00373-011-1023-4","volume":"27","author":"J Akiyama","year":"2011","unstructured":"Akiyama, J., Ito, H., Kobayashi, M., Nakamura, G.: Arrangements of $$n$$ points whose incident-line-numbers are at most $$n\/2$$. Graphs Combin. 27(3), 321\u2013326 (2011)","journal-title":"Graphs Combin."},{"issue":"3\u20134","key":"487_CR5","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF02579184","volume":"3","author":"J Beck","year":"1983","unstructured":"Beck, J.: On the lattice property of the plane and some problems of Dirac, Motzkin and Erd\u0151s in combinatorial geometry. Combinatorica 3(3\u20134), 281\u2013297 (1983)","journal-title":"Combinatorica"},{"issue":"2","key":"487_CR6","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/s10998-017-0224-x","volume":"77","author":"J Bokowski","year":"2018","unstructured":"Bokowski, J., Pokora, P.: On the Sylvester\u2013Gallai and the orchard problem for pseudoline arrangements. Period. Math. Hungar. 77(2), 164\u2013174 (2018)","journal-title":"Period. Math. Hungar."},{"issue":"2\u20133","key":"487_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02112289","volume":"40","author":"P Borwein","year":"1990","unstructured":"Borwein, P., Moser, W.O.J.: A survey of Sylvester\u2019s problem and its generalizations. Aequationes Math. 40(2\u20133), 111\u2013135 (1990)","journal-title":"Aequationes Math."},{"key":"487_CR8","volume-title":"Research Problems in Discrete Geometry","author":"P Brass","year":"2005","unstructured":"Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005)"},{"key":"487_CR9","unstructured":"de Bruijn, N.G., Erd\u00f6s, P.: On a combinatorial problem. Nederl. Akad. Wetensch., Proc. 51, 1277\u20131279 (1948)"},{"key":"487_CR10","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1080\/00029890.1970.11992442","volume":"77","author":"GD Chakerian","year":"1970","unstructured":"Chakerian, G.D.: Sylvester\u2019s problem on collinear points and a relative. Amer. Math. Monthly 77, 164\u2013167 (1970)","journal-title":"Amer. Math. Monthly"},{"key":"487_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/9781108912181","volume-title":"The Discrete Mathematical Charms of Paul Erd\u0151s\u2014A Simple Introduction","author":"V Chv\u00e1tal","year":"2021","unstructured":"Chv\u00e1tal, V.: The Discrete Mathematical Charms of Paul Erd\u0151s\u2014A Simple Introduction. Cambridge University Press, Cambridge (2021)"},{"key":"487_CR12","doi-asserted-by":"crossref","unstructured":"Croft, H.T., Falconer, K.J., Guy, R.K.: Unsolved Problems in Geometry. Problem Books in Mathematics. Unsolved Problems in Intuitive Mathematics, vol.\u00a02. Springer, New York (1991)","DOI":"10.1007\/978-1-4612-0963-8"},{"issue":"2","key":"487_CR13","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF02189318","volume":"9","author":"J Csima","year":"1993","unstructured":"Csima, J., Sawyer, E.T.: There exist $$6n\/13$$ ordinary points. Discrete Comput. Geom. 9(2), 187\u2013202 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"487_CR14","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1093\/qmath\/2.1.221","volume":"2","author":"GA Dirac","year":"1951","unstructured":"Dirac, G.A.: Collinearity properties of sets of points. Quart. J. Math. Oxford Ser. 2, 221\u2013227 (1951)","journal-title":"Quart. J. Math. Oxford Ser."},{"key":"487_CR15","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., T\u00f3th, Cs.D.: Distinct triangle areas in a planar point set. In: 12th International Conference on Integer Programming and Combinatorial Optimization (Ithaca 2007). Lecture Notes in Comput. Sci., vol. 4513, pp. 119\u2013129. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-72792-7_10"},{"key":"487_CR16","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer, Berlin (1987)","DOI":"10.1007\/978-3-642-61568-9"},{"issue":"1","key":"487_CR17","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0097-3165(85)90017-2","volume":"38","author":"H Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H., Welzl, E.: On the number of line separations of a finite set in the plane. J. Combin. Theory Ser. A 38(1), 15\u201329 (1985)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"1","key":"487_CR18","doi-asserted-by":"crossref","first-page":"65","DOI":"10.2307\/2304011","volume":"50","author":"P Erd\u00f6s","year":"1943","unstructured":"Erd\u00f6s, P.: Problem 4065. Amer. Math. Monthly 50(1), 65 (1943)","journal-title":"Amer. Math. Monthly"},{"key":"487_CR19","unstructured":"Erd\u0151s, P.: Some unsolved problems. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl. 6, 221\u2013254 (1961)"},{"key":"487_CR20","unstructured":"Erd\u0151s, P., Purdy, G.: Extremal problems in combinatorial geometry. In: Handbook of Combinatorics, vol.\u00a01, pp. 809\u2013874 (chapter 17). Elsevier, Amsterdam (1995)"},{"key":"487_CR21","first-page":"463","volume":"2","author":"P Erd\u00f6s","year":"1935","unstructured":"Erd\u00f6s, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Math. 2, 463\u2013470 (1935)","journal-title":"Compositio Math."},{"key":"487_CR22","unstructured":"Erd\u0151s, P., Szekeres, G.: On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest. E\u00f6tv\u00f6s Sect. Math. 3\u20134, 53\u201362 (1960)"},{"key":"487_CR23","doi-asserted-by":"crossref","unstructured":"Felsner, S.: Geometric Graphs and Arrangements. Some Chapters from Combinatorial Geometry. Advanced Lectures in Mathematics. Friedr. Vieweg & Sohn, Wiesbaden (2004)","DOI":"10.1007\/978-3-322-80303-0"},{"key":"487_CR24","unstructured":"Felsner, S., Goodman, J.E.: Pseudoline arrangements. In: Handbook of Discrete and Computational Geometry, 3rd ed., pp. 125\u2013157 (chapter\u00a05). CRC Press, Boca Raton (2018)"},{"issue":"3","key":"487_CR25","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/s00454-011-9366-4","volume":"46","author":"S Felsner","year":"2011","unstructured":"Felsner, S., Valtr, P.: Coding and counting arrangements of pseudolines. Discrete Comput. Geom. 46(3), 405\u2013416 (2011)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"487_CR26","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1090\/S0002-9939-1984-0760946-2","volume":"92","author":"Z F\u00fcredi","year":"1984","unstructured":"F\u00fcredi, Z., Pal\u00e1sti, I.: Arrangements of lines with a large number of triangles. Proc. Amer. Math. Soc. 92(4), 561\u2013566 (1984)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"2","key":"487_CR27","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0097-3165(80)90011-4","volume":"29","author":"JE Goodman","year":"1980","unstructured":"Goodman, J.E., Pollack, R.: On the combinatorial classification of nondegenerate configurations in the plane. J. Combin. Theory Ser. A 29(2), 220\u2013235 (1980)","journal-title":"J. Combin. Theory Ser. A"},{"key":"487_CR28","first-page":"383","volume":"32","author":"JE Goodman","year":"1981","unstructured":"Goodman, J.E., Pollack, R.: A combinatorial perspective on some problems in geometry. Congr. Numer. 32, 383\u2013394 (1981)","journal-title":"Congr. Numer."},{"key":"487_CR29","doi-asserted-by":"crossref","unstructured":"Goodman, J.E., Pollack, R.: Allowable sequences and order types in discrete and computational geometry. In: New Trends in Discrete and Computational Geometry. Algorithms Combin., vol. 10, pp. 103\u2013134. Springer, Berlin (1993)","DOI":"10.1007\/978-3-642-58043-7_6"},{"issue":"2","key":"487_CR30","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00454-013-9518-9","volume":"50","author":"B Green","year":"2013","unstructured":"Green, B., Tao, T.: On sets defining few ordinary lines. Discrete Comput. Geom. 50(2), 409\u2013468 (2013)","journal-title":"Discrete Comput. Geom."},{"key":"487_CR31","doi-asserted-by":"crossref","unstructured":"Gr\u00fcnbaum, B.: Arrangements and Spreads. Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, vol. 10. American Mathematical Society, Providence (1972)","DOI":"10.1090\/cbms\/010"},{"key":"487_CR32","doi-asserted-by":"crossref","unstructured":"Han, Z.: A note on the weak Dirac conjecture. Electron. J. Combin. 24(1), #\u00a0P1.63 (2017)","DOI":"10.37236\/6688"},{"issue":"12","key":"487_CR33","doi-asserted-by":"publisher","first-page":"3981","DOI":"10.4171\/jems\/1000","volume":"22","author":"AF Holmsen","year":"2020","unstructured":"Holmsen, A.F., Mojarrad, H.N., Pach, J., Tardos, G.: Two extensions of the Erd\u0151s\u2013Szekeres problem. J. Eur. Math. Soc. 22(12), 3981\u20133995 (2020)","journal-title":"J. Eur. Math. Soc."},{"key":"487_CR34","doi-asserted-by":"publisher","first-page":"210","DOI":"10.4153\/CJM-1958-024-6","volume":"10","author":"LM Kelly","year":"1958","unstructured":"Kelly, L.M., Moser, W.O.J.: On the number of ordinary lines determined by $$n$$ points. Canadian J. Math. 10, 210\u2013219 (1958)","journal-title":"Canadian J. Math."},{"key":"487_CR35","doi-asserted-by":"crossref","unstructured":"Klee, V., Wagon, S.: Old and New Unsolved Problems in Plane Geometry and Number Theory. The Dolciani Mathematical Expositions, vol. 11. Mathematical Association of America, Washington (1991)","DOI":"10.1090\/dol\/011"},{"key":"487_CR36","doi-asserted-by":"crossref","unstructured":"Knuth, D.E.: Axioms and Hulls. Lecture Notes in Computer Science, vol. 606. Springer, Berlin (1992)","DOI":"10.1007\/3-540-55611-7"},{"key":"487_CR37","doi-asserted-by":"crossref","unstructured":"Leighton, F.Th.: New lower bound techniques for VLSI. Math. Systems Theory 17(1), 47\u201370 (1984)","DOI":"10.1007\/BF01744433"},{"key":"487_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511987045","volume-title":"A Course in Combinatorics","author":"JH van Lint","year":"2001","unstructured":"van Lint, J.H., Wilson, R.M.: A Course in Combinatorics. Cambridge University Press, Cambridge (2001)"},{"key":"487_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511569340","volume-title":"A Book of Curves","author":"EH Lockwood","year":"1961","unstructured":"Lockwood, E.H.: A Book of Curves. Cambridge University Press, New York (1961)"},{"key":"487_CR40","doi-asserted-by":"crossref","unstructured":"Lund, B., Purdy, G.B., Smith, J.W.: A pseudoline counterexample to the strong Dirac conjecture. Electron. J. Combin. 21(2), #\u00a0P2.31 (2014)","DOI":"10.37236\/4015"},{"issue":"3","key":"487_CR41","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1090\/S0002-9947-1951-0041447-9","volume":"70","author":"Th Motzkin","year":"1951","unstructured":"Motzkin, Th.: The lines and planes connecting the points of a finite set. Trans. Amer. Math. Soc. 70(3), 451\u2013464 (1951)","journal-title":"Trans. Amer. Math. Soc."},{"key":"487_CR42","unstructured":"Motzkin, Th.S.: Nonmixed connecting lines. Abstract 67T-605. Notices Amer. Math. Soc. 14(6), 837 (1967)"},{"key":"487_CR43","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0097-3165(75)90045-X","volume":"18","author":"ThS Motzkin","year":"1975","unstructured":"Motzkin, Th.S.: Sets for which no point lies on many connecting lines. J. Combinatorial Theory Ser. A 18, 345\u2013348 (1975)","journal-title":"J. Combinatorial Theory Ser. A"},{"key":"487_CR44","unstructured":"Nilakantan, N.: Extremal problems related to the Sylvester\u2013Gallai theorem. In: Combinatorial and Computational Geometry. Math. Sci. Res. Inst. Publ., vol. 52, pp. 479\u2013494. Cambridge University Press, Cambridge (2005)"},{"issue":"4","key":"487_CR45","first-page":"215","volume":"107","author":"J Pach","year":"2005","unstructured":"Pach, J.: Directions in combinatorial geometry. Jahresber. Deutsch. Math.-Verein. 107(4), 215\u2013225 (2005)","journal-title":"Jahresber. Deutsch. Math.-Verein."},{"issue":"4","key":"487_CR46","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s00454-006-1264-9","volume":"36","author":"J Pach","year":"2006","unstructured":"Pach, J., Radoi\u010di\u0107, R., Tardos, G., T\u00f3th, G.: Improving the crossing lemma by finding more crossings in sparse graphs. Discrete Comput. Geom. 36(4), 527\u2013552 (2006)","journal-title":"Discrete Comput. Geom."},{"key":"487_CR47","doi-asserted-by":"crossref","unstructured":"Pach, J., Sharir, M.: Combinatorial Geometry and its Algorithmic Applications. Mathematical Surveys and Monographs, vol. 152. American Mathematical Society, Providence (2009)","DOI":"10.1090\/surv\/152"},{"key":"487_CR48","unstructured":"Payne, M.S.: Combinatorial Geometry of Point Sets with Collinearities. PhD thesis, University of Melbourne (2014)"},{"key":"487_CR49","doi-asserted-by":"crossref","unstructured":"Payne, M.S., Wood, D.R.: Progress on Dirac\u2019s conjecture. Electron. J. Combin. 21(2), #\u00a0P2.12 (2014)","DOI":"10.37236\/3722"},{"key":"487_CR50","unstructured":"Pham, H.H., Phi, T.C.: A new progress on weak Dirac conjecture (2016). arXiv:1607.08398"},{"issue":"21","key":"487_CR51","doi-asserted-by":"publisher","first-page":"2456","DOI":"10.1016\/j.disc.2013.07.008","volume":"313","author":"R Pinchasi","year":"2013","unstructured":"Pinchasi, R.: Crossing by lines all edges of a line arrangement. Discrete Math. 313(21), 2456\u20132462 (2013)","journal-title":"Discrete Math."},{"issue":"2","key":"487_CR52","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF00147438","volume":"9","author":"JF Rigby","year":"1980","unstructured":"Rigby, J.F.: Multiple intersections of diagonals of regular polygons, and related topics. Geom. Dedicata 9(2), 207\u2013238 (1980)","journal-title":"Geom. Dedicata"},{"issue":"4","key":"487_CR53","doi-asserted-by":"publisher","first-page":"1047","DOI":"10.1090\/jams\/869","volume":"30","author":"A Suk","year":"2017","unstructured":"Suk, A.: On the Erd\u0151s\u2013Szekeres convex polygon problem. J. Amer. Math. Soc. 30(4), 1047\u20131053 (2017)","journal-title":"J. Amer. Math. Soc."},{"key":"487_CR54","first-page":"98","volume":"59","author":"J Sylvester","year":"1893","unstructured":"Sylvester, J.: Mathematical Question 11851. Educational Times 59, 98 (1893)","journal-title":"Educational Times"},{"issue":"3","key":"487_CR55","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1017\/S0963548397002976","volume":"6","author":"LA Sz\u00e9kely","year":"1997","unstructured":"Sz\u00e9kely, L.A.: Crossing numbers and hard Erd\u0151s problems in discrete geometry. Combin. Probab. Comput. 6(3), 353\u2013358 (1997)","journal-title":"Combin. Probab. Comput."},{"issue":"3\u20134","key":"487_CR56","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/BF02579194","volume":"3","author":"E Szemer\u00e9di","year":"1983","unstructured":"Szemer\u00e9di, E., Trotter, W.T., Jr.: Extremal problems in discrete geometry. Combinatorica 3(3\u20134), 381\u2013392 (1983)","journal-title":"Combinatorica"},{"issue":"3","key":"487_CR57","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0097-3165(82)90045-0","volume":"33","author":"P Ungar","year":"1982","unstructured":"Ungar, P.: $$2N$$ noncollinear points determine at least $$2N$$ directions. J. Combin. Theory Ser. A 33(3), 343\u2013347 (1982)","journal-title":"J. Combin. Theory Ser. A"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00487-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00487-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00487-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T23:04:17Z","timestamp":1727391857000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00487-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,7]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["487"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00487-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,4,7]]},"assertion":[{"value":"11 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}