Generalizations of the Crossing Lemma
Géza Tóth HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary Budapest University of Technology and Economics, SZIT, Budapest, Hungary [email protected] · 2025
Read Generalizations of the Crossing Lemma by Géza Tóth HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary Budapest University of Technology and Economics, SZIT, Budapest, Hungary [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-14074.txt.
Introduction
Geza Toth reviews generalizations of the Crossing Lemma in a solo 2025 combinatorics paper. Draw any graph in the plane and edges must cross. The crossing number counts the fewest crossings achievable. The Crossing Lemma, proved over forty years ago, gives a tight lower bound on that number. The bound comes from the counts of vertices and edges alone. The lemma remains the most important inequality in the area.
Toth surveys how the lemma has been extended since its proof. The extensions span different graph classes, drawing surfaces, and refined counting schemes. He also collects its applications in geometry and combinatorics. As a review, the paper's value is the map it draws. It shows which generalizations are known and where the lemma's reach powers other results. A single simple inequality became a load-bearing tool for discrete geometry.
Catalog record
| CREATOR | Géza Tóth HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary Budapest University of Technology and Economics, SZIT, Budapest, Hungary [email protected] |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-14074
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generalizations of the Crossing Lemma Géza Tóth HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary Budapest University of Technology and Economics, SZIT, Budapest, Hungary [email protected] Abstract The crossing number of a graph is the minimum number of crossings over all of its drawings on the plane. The Crossing Lemma, proved more than 40 years ago, is a tight lower bound on the crossing number of a graph in terms of the number of vertices and edges. It is definitely the most important inequality on crossing numbers. We review some generalizations and applications of the Crossing Lemma. 0.1 Introduction The crossing number {\mbox{\sc cr}}(G) of G is the minimum number of edge crossings over all drawings of G on the plane. It has a fascinating history and lots of applications in theory and practice. It started with Turán’s Brick Factory problem in 1944, also known as Zarankiewicz’s problem Guy 69 . Determining or even estimating the crossing number is a notoriously difficult problem GJ 83 ; Sch 18 , and it has a huge number of practical and theoretical applications Szé 97 ; DLM 19 in VLSI design, geographic information systems, graph drawing, computer graphics, and many other fields. Even the crossing numbers of complete graphs are not known, despite the huge number of results, attempts, improvements BLS 19 ; HH 62 ; ACFM+ 12 ; ADFM+ 20 . The Crossing Lemma of Ajtai, Chvátal, Newborn, Szemerédi and independently Leighton, 40 years ago was a real breakthrough. It is a general lower bound on the crossing number, it states that any simple graph with n vertices and e\geq 4n edges has crossing number at least ce^{3}/n^{2} for some c>0 . Székely Szé 97 and then others observed that crossing numbers, in particular the Crossing Lemma, also has important applications in the theory of incidences ST 01 , additive number theory Ele 97 , in the analysis of geometric algorithms Dey 98 and many other fields. In this paper we survey some results related to the Crossing Lemma and its generalizations. It Section 2 we review the history and improvements of the Crossing Lemma. It is easy to see that it does not hold for multigraphs in general, not even in any weaker form. In Section 3 we investigate its generalizations for multigraphs under different conditions on the drawing. In Section 4 we try to figure out, how far can we go with such a generalization, that is, what could be the weakest condition which implies some Crossing Lemma type statement. Finally, in Section 5 we introduce some other versions of the crossing number, the pair-crossing number and the odd-crossing number, their relationships, and generalizations of the Crossing Lemma for these crossing numbers. 0.2 The Crossing Lemma In a drawing of a graph (or multigraph) G , vertices are represented by points and edges are represented by curves connecting the corresponding points. If it does not lead to confusion, the points (curves), representing the vertices (edges) are also called vertices (edges). We assume that in a drawing an edge cannot contain a vertex in its interior, if two edges have a common point, then it is a common endpoint or a proper crossing, and three edges do not cross at the same point. For any graph G , n(G) and e(G) denote its number of vertices and edges, respectively. A graph (resp. multigraph), together with its drawing, is called a topological graph (resp. multigraph). The most important, fundamental result on crossing numbers is the Crossing Lemma, first proved by Ajtai, Chvátal, Newborn, Szemerédi, and Leighton, 40 years ago ACNS 82 ; Lei 83 . Theorem 0.2.1 (Crossing Lemma) For any simple graph G , if e(G)\geq 4n(G) then {\mbox{\sc cr}}(G)\geq\frac{1}{64}\frac{e(G)^{3}}{n(G)^{2}}. The original proofs were quite complicated and gave a much worse constant in the bound. The following beautiful proof is attributed to Chazelle, Sharir, and Welzl and appeared in ”Proofs from THE BOOK” AZ 99 . For the proof we need the following easy but very important statement (see e.g. PT00b ). Observation 1 For any simple graph G , in a drawing with exactly {\mbox{\sc cr}}(G) crossings, (i) no edge crosses itself, (ii) two edges have at most one common point. Proof (i) Suppose that an edge \alpha crosses itself at point p . Reverse the orientation of the part of \alpha between the two occurrences of p . Then p becomes a self-touching point. And now we can get rid of the touching by a slight perturbation at p . This way e get a drawing with fewer crossings, which is a contradiction. See Figure 1 . (ii) Suppose that two edges \alpha and \beta have two common points, p and q . One of them can be a crossing or a common endpoint, the other one is a crossing. Then swap the parts of the edges between p and q . Again, we get a drawing with fewer crossings, which is a contradiction. See Figure 1 Figure 1: Reducing the number of crossings. Proof (Proof of the Crossing Lemma) The proof goes in two steps. 1. First we show that for any graph G {\mbox{\sc cr}}(G)\geq e(G)-3n(G). (1) This can be proved by induction on e(G) . If e(G)\leq 3n(G) , then the statement holds trivially. Suppose that e(G)>3n(G) and we have already proved the statement for smaller values of e(G) . It is well-known consequence of Euler’s formula that a planar graph of n vertices has at most 3n-6 edges. Therefore, {\mbox{\sc cr}}(G)>0 . Remove an edge \alpha from G which contains a crossing. Then {\mbox{\sc cr}}(G)\geq{\mbox{\sc cr}}(G-\alpha)+1 and by the induction hypothesis, {\mbox{\sc cr}}(G-\alpha)\geq e(G)-1-3n(G) . Combining them, the statement follows. 2. Consider a drawing of G with {\mbox{\sc cr}}(G) crossings. Take a random induced subgraph G^{\prime} of G by selecting each vertex independently with probability p (whose value is determined later). We obtain a random subset of vertices U\subset V(G) and let G^{\prime} be the subgraph induced by U . Draw the edges of G^{\prime} as they were drawn in the original drawing. The number of vertices and edges of G^{\prime} , n(G^{\prime}) and e(G^{\prime}) are random variables, and E[n(G^{\prime})]=pn(G) , E[e(G^{\prime})]=p^{2}e(G) since each edge of G survives with probability p^{2} . Let X(G^{\prime}) be the number of crossings of G^{\prime} in the obtained drawing. Then clearly X(G^{\prime})\geq{\mbox{\sc cr}}(G^{\prime}) . By Observation 1 , only independent edges can cross in the original optimal drawing of G , consequently, also in G^{\prime} . A crossing is present in the drawing of G^{\prime} if all four corresponding endpoints are selected and the probability of this is p^{4} . (A crossing of two edges with a common endpoint would be present with probability p^{3} .) Therefore, E[X(G^{\prime})]=p^{4}{\mbox{\sc cr}}(G) . By 1 , {\mbox{\sc cr}}(G^{\prime})\geq e(G^{\prime})-3n(G^{\prime}) . Taking expectations, we get p^{4}{\mbox{\sc cr}}(G)=E[X(G^{\prime})]\geq E[{\mbox{\sc cr}}(G^{\prime})]\geq E[e(G^{\prime})]-3E[n(G^{\prime})]=p^{2}e(G)-3pn(G) so {\mbox{\sc cr}}(G)\geq e(G)/p^{2}-3n(G)/p^{3} . Set p=4n(G)/e(G) , by assumption p\leq 1 . Substitute in the last formula and we get {\mbox{\sc cr}}(G)\geq\frac{1}{64}e(G)^{3}/n(G)^{2}. This bound cannot be improved apart from the value of the constant. That is, there is a constant c with the following property. For any n , e , e\leq\binom{n}{2} , there is a graph G with n(G)=n , e(G)=e and