{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T02:21:44Z","timestamp":1778552504402,"version":"3.51.4"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T00:00:00Z","timestamp":1580083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T00:00:00Z","timestamp":1580083200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["FE 340\/11-1 and FE 340\/12-1"],"award-info":[{"award-number":["FE 340\/11-1 and FE 340\/12-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["Advanced Research Grant no. 267165 (DISCONV)"],"award-info":[{"award-number":["Advanced Research Grant no. 267165 (DISCONV)"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2021,1]]},"abstract":"Abstract<\/jats:title>A pseudocircle is a simple closed curve on the sphere or in the plane. The study of arrangements of pseudocircles was initiated by Gr\u00fcnbaum, who defined them as collections of simple closed curves that pairwise intersect in exactly two crossings. Gr\u00fcnbaum conjectured that the number of triangular cells $$p_3$$<\/jats:tex-math>\n \n p<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in digon-free arrangements of n<\/jats:italic> pairwise intersecting pseudocircles is at least $$2n-4$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n -<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We present examples to disprove this conjecture. With a recursive construction based on an example with\u00a012 pseudocircles and 16 triangles we obtain a family of intersecting digon-free arrangements with $$p_3({\\mathscr {A}})\/n \\rightarrow 16\/11 = 1.\\overline{45}$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n \n (<\/mml:mo>\n A<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \/<\/mml:mo>\n n<\/mml:mi>\n \u2192<\/mml:mo>\n 16<\/mml:mn>\n \/<\/mml:mo>\n 11<\/mml:mn>\n =<\/mml:mo>\n 1<\/mml:mn>\n .<\/mml:mo>\n \n 45<\/mml:mn>\n \u00af<\/mml:mo>\n <\/mml:mover>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We expect that the lower bound $$p_3({\\mathscr {A}}) \\ge 4n\/3$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n \n (<\/mml:mo>\n A<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n 4<\/mml:mn>\n n<\/mml:mi>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is tight for infinitely many simple arrangements. It may however be true that all digon-free arrangements of\u00a0n<\/jats:italic> pairwise intersecting circles have at least $$2n-4$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n n<\/mml:mi>\n -<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> triangles. For pairwise intersecting arrangements with digons we have a lower bound of $$p_3 \\ge 2n\/3$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n \u2265<\/mml:mo>\n 2<\/mml:mn>\n n<\/mml:mi>\n \/<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and conjecture that $$p_3 \\ge n-1$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n \u2265<\/mml:mo>\n n<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Concerning the maximum number of triangles in pairwise intersecting arrangements of pseudocircles, we show that $$p_3 \\le \\frac{4}{3}\\left( {\\begin{array}{c}n\\\\ 2\\end{array}}\\right) +O(n)$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n \u2264<\/mml:mo>\n \n 4<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n \n \n \n \n \n n<\/mml:mi>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n +<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This is essentially best possible because there are families of pairwise intersecting arrangements of n<\/jats:italic> pseudocircles with $$p_3 = \\frac{4}{3}\\left( {\\begin{array}{c}n\\\\ 2\\end{array}}\\right) $$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msub>\n =<\/mml:mo>\n \n 4<\/mml:mn>\n 3<\/mml:mn>\n <\/mml:mfrac>\n \n \n \n \n \n n<\/mml:mi>\n <\/mml:mtd>\n <\/mml:mtr>\n \n \n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The paper contains many drawings of arrangements of pseudocircles and a good fraction of these drawings was produced automatically from the combinatorial data produced by our generation algorithm. In the final section we describe some aspects of the drawing algorithm.<\/jats:p>","DOI":"10.1007\/s00454-020-00173-4","type":"journal-article","created":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T18:03:37Z","timestamp":1580148217000},"page":"261-278","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Arrangements of Pseudocircles: Triangles and Drawings"],"prefix":"10.1007","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6150-1998","authenticated-orcid":false,"given":"Stefan","family":"Felsner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1657-9796","authenticated-orcid":false,"given":"Manfred","family":"Scheucher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,1,27]]},"reference":[{"issue":"2","key":"173_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/972639.972641","volume":"51","author":"PK Agarwal","year":"2004","unstructured":"Agarwal, P.K., Nevo, E., Pach, J., Pinchasi, R., Sharir, M., Smorodinsky, S.: Lenses in arrangements of pseudo-circles and their applications. J. ACM 51(2), 139\u2013186 (2004)","journal-title":"J. ACM"},{"key":"173_CR2","volume-title":"Oriented Matroids. Encyclopedia of Mathematics and its Applications","author":"A Bj\u00f6rner","year":"1993","unstructured":"Bj\u00f6rner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Encyclopedia of Mathematics and its Applications, vol. 46. Cambridge University Press, Cambridge (1993)"},{"issue":"1","key":"173_CR3","first-page":"5","volume":"21","author":"J Blanc","year":"2011","unstructured":"Blanc, J.: The best polynomial bounds for the number of triangles in a simple arrangement of $$n$$ pseudo-lines. Geombinatorics 21(1), 5\u201314 (2011)","journal-title":"Geombinatorics"},{"key":"173_CR4","unstructured":"Cheong, O.: The Ipe extensible drawing editor. http:\/\/ipe.otfried.org\/"},{"key":"173_CR5","volume-title":"Handbook of Discrete and Computational Geometry","author":"S Felsner","year":"2018","unstructured":"Felsner, S., Goodman, J.E.: Pseudoline arrangements. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry, 3rd edn. CRC Press, Boca Raton (2018)","edition":"3"},{"key":"173_CR6","doi-asserted-by":"crossref","unstructured":"Felsner, S., Kriegel, K.: Triangles in Euclidean arrangements. In: Hromkovi\u010d, J., S\u00fdkora, O. (eds.) Proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201998). Lecture Notes in Computer Science, vol. 1517, pp. 137\u2013148. Springer, Berlin (1998)","DOI":"10.1007\/10692760_12"},{"key":"173_CR7","unstructured":"Felsner, S., Scheucher, M.: Webpage: Homepage of Pseudocircles. http:\/\/www3.math.tu-berlin.de\/pseudocircles"},{"key":"173_CR8","unstructured":"Felsner, S., Scheucher, M.: Triangles in arrangements of pseudocircles. In: Proceedings of the 33rd European Workshop on Computational Geometry (EuroCG\u201917), pp. 225\u2013228 (2017). http:\/\/csconferences.mah.se\/eurocg2017\/proceedings.pdf"},{"key":"173_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00077-y","author":"S Felsner","year":"2019","unstructured":"Felsner, S., Scheucher, M.: Arrangements of pseudocircles: on circularizability. Discrete Comput. Geom. (2019). https:\/\/doi.org\/10.1007\/s00454-019-00077-y. (Ricky Pollack Memorial Issue)","journal-title":"Discrete Comput. Geom."},{"key":"173_CR10","volume-title":"Arrangements and Spreads. Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics","author":"B Gr\u00fcnbaum","year":"1972","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). (reprinted 1980)"},{"key":"173_CR11","first-page":"256","volume":"78","author":"F Levi","year":"1926","unstructured":"Levi, F.: Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade. Ber. Math. Phys. Kl. s\u00e4chs. Akad. Wiss. Leipzig 78, 256\u2013267 (1926)","journal-title":"Ber. Math. Phys. Kl. s\u00e4chs. Akad. Wiss. Leipzig"},{"key":"173_CR12","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1090\/dimacs\/006\/21","volume-title":"Discrete and Computational Geometry","author":"J Snoeynik","year":"1991","unstructured":"Snoeynik, J., Hershberger, J.: Sweeping arrangements of curves. In: Goodman, J.E., Pollack, R., Steiger, W. (eds.) Discrete and Computational Geometry. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 6, pp. 309\u2013349. American Mathematical Society, Providence (1991)"},{"key":"173_CR13","unstructured":"Stein, W., et\u00a0al.: Sage Mathematics Software (Version 7.6). The Sage Development Team (2017). http:\/\/www.sagemath.org"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00173-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-020-00173-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-020-00173-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,26]],"date-time":"2021-01-26T00:14:42Z","timestamp":1611620082000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-020-00173-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,27]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["173"],"URL":"https:\/\/doi.org\/10.1007\/s00454-020-00173-4","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,27]]},"assertion":[{"value":"9 May 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 January 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 January 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}