{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T05:16:13Z","timestamp":1739855773487,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T00:00:00Z","timestamp":1737504000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T00:00:00Z","timestamp":1737504000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100006919","name":"Massachusetts Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006919","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,3]]},"abstract":"Abstract<\/jats:title>\n Determining whether there exists a graph such that its crossing number and pair crossing number are distinct is an important open problem in geometric graph theory. We show that \n \n $$\\textit{cr}(G)=O(\\mathop {\\textrm{pcr}}(G)^{3\/2})$$<\/jats:tex-math>\n \n \n cr<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n pcr<\/mml:mtext>\n \n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n 3<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for every graph G<\/jats:italic>, improving the previous best bound by a logarithmic factor. Answering a question of Pach and T\u00f3th, we prove that the bisection width (and, in fact, the cutwidth as well) of a graph G<\/jats:italic> with degree sequence \n \n $$d_1,d_2,\\dots ,d_n$$<\/jats:tex-math>\n \n \n \n d<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n d<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n \n d<\/mml:mi>\n n<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> satisfies \n \n $$\\mathop {\\textrm{bw}}(G)=O\\big (\\sqrt{\\mathop {\\textrm{pcr}}(G)+\\sum _{k=1}^n d_k^2}\\big )$$<\/jats:tex-math>\n \n \n bw<\/mml:mtext>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n \n pcr<\/mml:mtext>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n k<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msubsup>\n \n d<\/mml:mi>\n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:msqrt>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Then we show that there is a constant \n \n $$C\\ge 1$$<\/jats:tex-math>\n \n \n C<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that the following holds: For any graph G<\/jats:italic> of order n<\/jats:italic> and any set S<\/jats:italic> of at least \n \n $$n^C$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n C<\/mml:mi>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> points in general position on the plane, G<\/jats:italic> admits a straight-line drawing which maps the vertices to points of S<\/jats:italic> and has no more than \n \n $$O\\left( \\log n\\cdot \\left( \\mathop {\\textrm{pcr}}(G)+\\sum _{k=1}^n d_k^2\\right) \\right) $$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \n log<\/mml:mo>\n n<\/mml:mi>\n \u00b7<\/mml:mo>\n \n pcr<\/mml:mtext>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n k<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msubsup>\n \n d<\/mml:mi>\n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msubsup>\n <\/mml:mfenced>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> crossings. Our proofs rely on a slightly modified version of a separator theorem for string graphs by Lee, which might be of independent interest.<\/jats:p>","DOI":"10.1007\/s00454-024-00708-z","type":"journal-article","created":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T15:07:48Z","timestamp":1737558468000},"page":"310-326","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Pair Crossing Number, Cutwidth, and Good Drawings on Arbitrary Point Sets"],"prefix":"10.1007","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8399-3321","authenticated-orcid":false,"given":"Oriol Sol\u00e9","family":"Pi","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"issue":"2","key":"708_CR1","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1006\/jctb.2000.1978","volume":"80","author":"J Pach","year":"2000","unstructured":"Pach, J., T\u00f3th, G.: Which crossing number is it anyway? J. Comb. Theory Ser. B 80(2), 225\u2013246 (2000)","journal-title":"J. Comb. Theory Ser. B"},{"key":"708_CR2","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-1-4614-0110-0_30","volume-title":"Thirty Essays on Geometric Graph Theory","author":"G T\u00f3th","year":"2013","unstructured":"T\u00f3th, G.: A better bound for the pair-crossing number. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 563\u2013567. Springer, New York (2013)"},{"key":"708_CR3","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1017\/S0963548313000400","volume":"23","author":"J Matou\u0161ek","year":"2013","unstructured":"Matou\u0161ek, J.: Near-optimal separators in string graphs. Comb. Probab. Comput. 23, 135\u2013139 (2013)","journal-title":"Comb. Probab. Comput."},{"key":"708_CR4","unstructured":"Karl, J., T\u00f3th, G.: A slightly better bound on the crossing number in terms of the pair-crossing number (2021). arXiv:2105.14319"},{"issue":"1","key":"708_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0167-9260(94)90021-3","volume":"17","author":"O S\u00fdkora","year":"1994","unstructured":"S\u00fdkora, O., Vrt\u2019o, I.: On VLSI layouts of the star graph and related networks. Integration 17(1), 83\u201393 (1994)","journal-title":"Integration"},{"issue":"1","key":"708_CR6","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF02086610","volume":"16","author":"J Pach","year":"1996","unstructured":"Pach, J., Shahrokhi, F., Szegedy, M.: Applications of the crossing number. Algorithmica 16(1), 111\u2013117 (1996)","journal-title":"Algorithmica"},{"key":"708_CR7","first-page":"194","volume":"9","author":"J Pach","year":"2000","unstructured":"Pach, J., T\u00f3th, G.: Thirteen problems on crossing numbers. Geombinatorics 9, 194\u2013207 (2000)","journal-title":"Geombinatorics"},{"issue":"1","key":"708_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.jctb.2003.09.002","volume":"92","author":"P Kolman","year":"2004","unstructured":"Kolman, P., Matou\u0161ek, J.: Crossing number, pair-crossing number, and expansion. J. Comb. Theory Ser. B 92(1), 99\u2013113 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"key":"708_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.7155\/jgaa.00069","volume":"7","author":"H Djidjev","year":"2003","unstructured":"Djidjev, H., Vrt\u2019o, I.: Crossing numbers and cutwidths. J. Graph Algorithms Appl. 7, 245\u2013251 (2003)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"708_CR10","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s4540010011","volume":"24","author":"J Pach","year":"2000","unstructured":"Pach, J., Spencer, J., T\u00f3th, G.: New bounds on crossing numbers. Discrete Comput. Geom. 24(4), 623\u2013644 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"708_CR11","doi-asserted-by":"crossref","unstructured":"Pach, J., Tardos, G.: Untangling a polygon. In: International Symposium on Graph Drawing, pp. 154\u2013161 (2001). Springer, New York","DOI":"10.1007\/3-540-45848-4_13"},{"issue":"2","key":"708_CR12","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"SN Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. Syst. Sci. 28(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"708_CR13","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1137\/S0097539700373520","volume":"32","author":"G Even","year":"2002","unstructured":"Even, G., Guha, S., Schieber, B.: Improved approximations of crossings in graph drawings and VLSI layout areas. SIAM J. Comput. 32(1), 231\u2013252 (2002)","journal-title":"SIAM J. Comput."},{"key":"708_CR14","doi-asserted-by":"crossref","unstructured":"Shahrokhi, F., S\u00fdkora, O., Sz\u00e9kely, L., Vrt\u2019o, I.: The gap between crossing numbers and convex crossing numbers (2004)","DOI":"10.1090\/conm\/342\/06145"},{"key":"708_CR15","first-page":"463","volume":"2","author":"P Erd\u00f6s","year":"1935","unstructured":"Erd\u00f6s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"708_CR16","unstructured":"Lee, J.R.: Separators in region intersection graphs. In: ITCS (2017)"},{"issue":"3","key":"708_CR17","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1017\/S0963548309990459","volume":"19","author":"J Fox","year":"2010","unstructured":"Fox, J., Pach, J.: A separator theorem for string graphs and its applications. Comb. Probab. Comput. 19(3), 371\u2013390 (2010)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"708_CR18","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/PL00009350","volume":"19","author":"I B\u00e1r\u00e1ny","year":"1998","unstructured":"B\u00e1r\u00e1ny, I., Valtr, P.: A positive fraction erdos-szekeres theorem. Discrete Comput. Geom. 19(3), 335\u2013342 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"708_CR19","doi-asserted-by":"publisher","first-page":"2199","DOI":"10.1137\/15M1007355","volume":"45","author":"J Fox","year":"2016","unstructured":"Fox, J., Pach, J., Suk, A.: A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing. SIAM J. Comput. 45(6), 2199\u20132223 (2016)","journal-title":"SIAM J. Comput."},{"key":"708_CR20","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0304-0208(08)73484-4","volume":"60","author":"M Ajtai","year":"1982","unstructured":"Ajtai, M., Chv\u00e1tal, V., Newborn, M., Szemer\u00e9di, E.: Crossing-free subgraphs. N.-Holl. Math. Stud. 60, 9\u201312 (1982)","journal-title":"N.-Holl. Math. Stud."},{"key":"708_CR21","volume-title":"Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks","author":"FT Leighton","year":"1983","unstructured":"Leighton, F.T.: Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks. MIT Press, Cambridge (1983)"},{"key":"708_CR22","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P., Salazar, G.: Approximating the crossing number of toroidal graphs. In: International Symposium on Algorithms and Computation, pp. 148\u2013159 (2007). Springer, New York","DOI":"10.1007\/978-3-540-77120-3_15"},{"issue":"1","key":"708_CR23","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1006\/jctb.2000.2015","volume":"82","author":"HA Juarez","year":"2001","unstructured":"Juarez, H.A., Salazar, G.: Drawings of Cm $$\\times $$ Cn with one disjoint family II. J. Comb. Theory Ser. B 82(1), 161\u2013165 (2001)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"708_CR24","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1002\/1097-0118(200103)36:3<168::AID-JGT1004>3.0.CO;2-#","volume":"36","author":"E Garcia-Moreno","year":"2001","unstructured":"Garcia-Moreno, E., Salazar, G.: Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree. J. Graph Theory 36(3), 168\u2013173 (2001)","journal-title":"J. Graph Theory"},{"issue":"2","key":"708_CR25","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1137\/05062706X","volume":"20","author":"D Bokal","year":"2006","unstructured":"Bokal, D., Fijavz, G., Mohar, B.: The minor crossing number. SIAM J. Discrete Math. 20(2), 344\u2013356 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"708_CR26","doi-asserted-by":"crossref","unstructured":"Wood, D.R., Telle, J.A.: Planar decompositions and the crossing number of graphs with an excluded minor. In: International Symposium on Graph Drawing, pp. 150\u2013161 (2006). Springer, New York","DOI":"10.1007\/978-3-540-70904-6_16"},{"key":"708_CR27","doi-asserted-by":"crossref","unstructured":"Hlin\u011bn\u00fd, P., Salazar, G.: On the crossing number of almost planar graphs. In: International Symposium on Graph Drawing, pp. 162\u2013173 (2006). Springer, New York","DOI":"10.1007\/978-3-540-70904-6_17"},{"key":"708_CR28","first-page":"569","volume":"52","author":"P Valtr","year":"2005","unstructured":"Valtr, P.: On the pair-crossing number. Comb. Comput. Geom. 52, 569\u2013575 (2005)","journal-title":"Comb. Comput. Geom."},{"key":"708_CR29","doi-asserted-by":"crossref","unstructured":"Pelsmajer, M.J., Schaefer, M., \u0160tefankov\u010d, D.: Odd crossing number and crossing number are not the same. Discrete Comput. Geom. 1\u201313 (2009)","DOI":"10.1007\/978-0-387-87363-3_23"},{"issue":"4","key":"708_CR30","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/s00454-007-9024-z","volume":"39","author":"G T\u00f3th","year":"2008","unstructured":"T\u00f3th, G.: Note on the pair-crossing number and the odd-crossing number. Discrete Comput. Geom. 39(4), 791\u2013799 (2008)","journal-title":"Discrete Comput. Geom."},{"key":"708_CR31","doi-asserted-by":"crossref","unstructured":"Pach, J., T\u00f3th, G.: Disjoint edges in topological graphs. In: Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory, pp. 133\u2013140 (2003). Springer, New York","DOI":"10.1007\/978-3-540-30540-8_15"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00708-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00708-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00708-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,17]],"date-time":"2025-02-17T23:52:59Z","timestamp":1739836379000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00708-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,22]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["708"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00708-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2025,1,22]]},"assertion":[{"value":"13 September 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}