{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:18:06Z","timestamp":1759331886363,"version":"build-2065373602"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T00:00:00Z","timestamp":1717459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T00:00:00Z","timestamp":1717459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003006","name":"Eidgen\u00f6ssische Technische Hochschule Z\u00fcrich","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003006","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swiss Federal Institute of Technology Zurich"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>A set <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$${\\mathcal {G}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>G<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> of planar graphs on the same number <jats:italic>n<\/jats:italic> of vertices is called <jats:italic>simultaneously embeddable<\/jats:italic> if there exists a set <jats:italic>P<\/jats:italic> of <jats:italic>n<\/jats:italic> points in the plane such that every graph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$G \\in {\\mathcal {G}}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> admits a (crossing-free) straight-line embedding with vertices placed at points of <jats:italic>P<\/jats:italic>. A <jats:italic>conflict collection<\/jats:italic> is a set of planar graphs of the same order with no simultaneous embedding. A well-known open problem from 2007 posed by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw and Mitchell, asks whether there exists a conflict collection of size 2. While this remains widely open, we give a short proof that for sufficiently large <jats:italic>n<\/jats:italic> there exists a conflict collection consisting of at most <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$(3+o(1))\\log _2(n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mn>3<\/mml:mn>\n                      <mml:mo>+<\/mml:mo>\n                      <mml:mi>o<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:msub>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> planar graphs on <jats:italic>n<\/jats:italic>\u00a0vertices. This constitutes a double-exponential improvement over the previously best known bound of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(n\\cdot 4^{n\/11})$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>4<\/mml:mn>\n                      <mml:mrow>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>11<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> for the same problem by Goenka et al. (Graphs Combin 39:100, 2023). Using our method we also provide a computer-free proof that for every integer <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n\\in [107,193]$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mn>107<\/mml:mn>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mn>193<\/mml:mn>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> there exists a conflict collection of 30 planar <jats:italic>n<\/jats:italic>-vertex graphs, improving upon the previously smallest known conflict collection consisting of 49 graphs of order 11, which was found using heavy computer assistance. While the construction by Goenka et al.\u00a0was explicit, our construction of a conflict collection of size <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is based on the probabilistic method and is thus only implicit. Motivated by this, for every large enough <jats:italic>n<\/jats:italic> we give a different, fully explicit construction of a collection of less than <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$n^6$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mn>6<\/mml:mn>\n                  <\/mml:msup>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> planar <jats:italic>n<\/jats:italic>-vertex graphs with no simultaneous embedding.<\/jats:p>","DOI":"10.1007\/s00454-024-00665-7","type":"journal-article","created":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T16:16:45Z","timestamp":1717517805000},"page":"743-757","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Logarithmic Bound for Simultaneous Embeddings of Planar Graphs"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4234-6136","authenticated-orcid":false,"given":"Raphael","family":"Steiner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,4]]},"reference":[{"key":"665_CR1","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1021231927255","volume":"19","author":"O Aichholzer","year":"2002","unstructured":"Aichholzer, O., Aurenhammer, F., Krasser, H.: Enumerating order types for small point sets with applications. Order 19, 265\u2013281 (2002)","journal-title":"Order"},{"issue":"1","key":"665_CR2","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1112\/S0025579300013875","volume":"33","author":"N Alon","year":"1986","unstructured":"Alon, N.: The number of polytopes, configurations and real matroids. Mathematika 33(1), 62\u201371 (1986)","journal-title":"Mathematika"},{"issue":"2","key":"665_CR3","doi-asserted-by":"publisher","first-page":"177","DOI":"10.7155\/jgaa.00318","volume":"18","author":"MJ Bannister","year":"2014","unstructured":"Bannister, M.J., Cheng, Z., Devanny, W.E., Eppstein, D.: Superpatterns and universal point sets. J. Graph Algorithms Appl. 18(2), 177\u2013209 (2014)","journal-title":"J. Graph Algorithms Appl."},{"key":"665_CR4","unstructured":"Bl\u00e4sius, T., Kobourov, S. G., Rutter, I.: Simultaneous embeddings of planar graphs. In R. Tamassia (ed.) Handbook of Graph Drawing and Visualization, Discrete Mathematics and Its Applications, pp. 349\u2013382. Chapman & Hall\/CRC, Boca Raton (2013)"},{"issue":"2","key":"665_CR5","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.comgeo.2006.05.006","volume":"36","author":"P Brass","year":"2007","unstructured":"Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D.P., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Comput. Geom. Theory Appl. 36(2), 117\u2013130 (2007)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"1","key":"665_CR6","doi-asserted-by":"publisher","first-page":"529","DOI":"10.7155\/jgaa.00374","volume":"19","author":"J Cardinal","year":"2015","unstructured":"Cardinal, J., Hoffmann, M., Kusters, V.: On universal point sets for planar graphs. J. Graph Algorithms Appl. 19(1), 529\u2013547 (2015)","journal-title":"J. Graph Algorithms Appl."},{"key":"665_CR7","first-page":"229","volume":"11","author":"I F\u00e1ry","year":"1948","unstructured":"F\u00e1ry, I.: On straight line representation of planar graphs. Acta Sci. Math. 11, 229\u2013233 (1948)","journal-title":"Acta Sci. Math."},{"issue":"1","key":"665_CR8","doi-asserted-by":"publisher","DOI":"10.1145\/3570636","volume":"70","author":"X Goaoc","year":"2023","unstructured":"Goaoc, X., Welzl, E.: Convex hulls of random order types. J. ACM 70(1), 8 (2023)","journal-title":"J. ACM"},{"key":"665_CR9","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/s00373-023-02699-9","volume":"39","author":"R Goenka","year":"2023","unstructured":"Goenka, R., Semnani, P., Yip, C.H.: An exponential bound for simultaneous embeddings of planar graphs. Graphs Combin. 39, 100 (2023)","journal-title":"Graphs Combin."},{"issue":"3","key":"665_CR10","doi-asserted-by":"publisher","first-page":"247","DOI":"10.7155\/jgaa.00529","volume":"24","author":"M Scheucher","year":"2020","unstructured":"Scheucher, M., Schrezenmaier, H., Steiner, R.: A note on universal point sets for planar graphs. J. Graph Algorithms Appl. 24(3), 247\u2013267 (2020)","journal-title":"J. Graph Algorithms Appl."},{"key":"665_CR11","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1090\/S0002-9947-1968-0226281-1","volume":"133","author":"HE Warren","year":"1968","unstructured":"Warren, H.E.: Lower bounds for approximation by nonlinear manifolds. Trans. Am. Math. Soc. 133, 167\u2013178 (1968)","journal-title":"Trans. Am. Math. Soc."},{"key":"665_CR12","doi-asserted-by":"publisher","first-page":"150","DOI":"10.2307\/2371086","volume":"54","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150\u2013168 (1932)","journal-title":"Am. J. Math."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00665-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00665-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00665-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T20:03:30Z","timestamp":1759262610000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00665-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,4]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["665"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00665-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,6,4]]},"assertion":[{"value":"13 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that no data has been used for the research presented in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}