WorksMathematics
Polynomial bounds for quasiplanar graphs
Abstract
A graph is -quasiplanar if it can be drawn in the plane without pairwise crossing edges. It was a longstanding conjecture that -vertex -quasiplanar graphs have edges. This was recently resolved by Sadhu and, independently, by Pach, Tardos, and Zeng, based on a theorem in topology proven by Beeker and Lazarovich. These papers showed that -quasiplanar graphs have at most edges. In this note, we greatly improve the dependence on and show that every -quasiplanar -vertex graph has at most edges. The proof is based on a geometric charging scheme and Erdős-Szekeres type combinatorial arguments.
Introduction
A graph is planar if it can be drawn in the plane with no two edges crossing. Planar graphs are among the most extensively studied graph families, both from a structural and an algorithmic perspective. A beautiful theorem of Fáry [10] (first proved by Wagner in 1936) is that every planar graph can be drawn in the plane with straight line segments as edges. Moreover, it follows from Euler’s polyhedral formula that the maximum number of edges of an -vertex planar graph is at most , which is optimal. This bound puts a heavy restriction on which graphs can be drawn without crossings.
A natural relaxation of planarity was introduced in the early 1990’s. A graph is -quasiplanar if it can be drawn in the plane such that no edges pairwise cross. Compared to planarity, which corresponds to the case , -quasiplanarity is much less understood for . The difficulty of this notion stems from the fact that -quasiplanar graphs can already exhibit strange behavior. For example, Brandenburg [6] showed that the complete graph is -quasiplanar, however, it has no -quasiplanar drawing with straight line segments. Furthermore, Ackerman and Tardos [2] showed that there exist -quasiplanar graphs such that in every -quasiplanar drawing, there are pairs of edges that cross more than once.
In the past three decades, the following question became one of the central problems in the theory of graph drawings.
What is the maximum number of edges of an -vertex -quasiplanar graph?
In 1996, Pach, Shahrokhi, and Szegedy [14] conjectured that for every fixed , this maximum is , and this conjecture was later reiterated by Brass, Moser and Pach [7]. The lack of very dense constructions of -quasiplanar graphs led to an even more ambitious folklore conjecture that the above maximum is . These conjectures proved to be very influential and played an important role in the development of modern combinatorial geometry. The attempts to resolve them led to a large number of different geometric and combinatorial techniques, including divide-and-conquer arguments, the use of partial orders, ordered graphs, and Davenport-Schinzel sequences, Ramsey-type arguments, charging schemes, and balanced separators.
We now give a (far from complete) overview of the history of results towards these conjectures. The case was confirmed by Agarwal, Aronov, Pach, Pollack, and Sharir [3] just a year later, and Ackerman and Tardos [2] proved that the maximum is between and . The case was then confirmed by Ackerman [1] in 2009. In general, the quasi-linear upper bound was proved by Pach, Shahrokhi, and Szegedy [14], which was later improved to by Fox and Pach [11]. Until recently, the best known bound was due to Fox, Pach, and Suk [12]. A notable corollary of this result is that if is an -vertex graph with at least edges, then any drawing of contains at least pairwise crossing edges for some .
The difficulty of the above conjectures led researchers to consider special drawings, which also proved to be quite difficult. The only fully understood case concerns drawings where the points are in convex position, and edges are straight line segments. In this case, Capoyleas and Pach [8] proved that the maximum number of edges is exactly . In the less restricted case, when the edges are straight-line segments or -monotone curves (and there is no assumption on the vertices), Valtr [19, 20] proved the bound . Furthermore, the sharper bound for straight line drawings follows from a work of Tóth [18].
The linear upper bound for the maximum number of edges of -quasiplanar graphs was finally established in recent works of Sadhu [16] and Pach, Tardos, and Zeng [15]. More precisely, it was independently discovered that this bound essentially follows from a topological result of Beeker and Lazarovich [5] from 2017. Since their work uses terminology quite different from that familiar to combinatorial geometers, and Beeker and Lazarovich were likely unaware of the quasiplanar graph conjecture, the connection remained unnoticed until it was uncovered with the help of large language models. The explicit bound is also established in [15], where the authors note that the dependence on is unlikely to be sharp.
Building on these recent works, we greatly improve the dependence on , and show the upper bound . This quantitatively improves all previous results for sufficiently large , even the bounds that only apply for the special case of straight line drawings. Our proof is also combinatorial and self-contained. As we were preparing to post this article, we have learned that, independently from our work, an updated version of Sadhu’s work [16] on arXiv also claims the improved bound.
Theorem 1.1. Let be a -quasiplanar -vertex graph. Then has at most edges.
This theorem has an interesting corollary for drawings of complete graphs as well. Somewhat surprisingly, the following simple question is already poorly understood. What is the minimum number of pairwise crossing edges in a straight line drawing of ? Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman [4] proved in 1991 that every such drawing contains at least pairwise crossing edges, while it is conjectured (see e.g. [7]) that the answer should be . The currently best known lower bound was established not long ago by Pach, Rubin, and Tardos [13]. Since their proof heavily relied on the fact that the edges are drawn as straight line segments, the authors asked about the minimum number of pairwise crossings in arbitrary drawings of . This problem is even less understood, and there is no known drawing of with fewer than linearly many pairwise crossing edges. The aforementioned result of Fox, Pach and Suk [12] gives a lower bound of . An immediate corollary of Theorem 1.1 sharpens this to by taking for a small constant .
The size of quasiplanar graphs
The general idea of the proof of Theorem 1.1 is as follows. We fix a drawing of our graph in which no edges pairwise cross, and we enclose the drawing in a sufficiently large disk. We then remove small neighborhoods of the vertices and (roughly speaking) triangulate the resulting region using triangles. Each curve corresponding to an edge of starts at a vertex, traverses some triangles of this triangulation and finishes at another vertex of . We define a charging rule that charges each curve to at least one of the edges or triangles it traverses. At the same time, using that in our drawing no edges pairwise cross, we show that the number of curves that are charged to any given edge or triangle is at most . This immediately implies that the number of edges of is at most times the number of triangles in our triangulation, i.e., .
Setup.
Formally, let be an -vertex -quasiplanar graph and fix a drawing of in which no edges pairwise cross. We identify the vertices of with the corresponding points in the plane, and the edges of with continuous curves, i.e., the images of continuous functions . A crossing between two curves is an intersection point that is not an endpoint of any of the curves. We make a few standard non-degeneracy assumptions: no curve goes through a vertex, curves are non-self intersecting, and no two curves touch, i.e., if two curves cross then one curve passes to the other side of the other curve. It is well known that a drawing can be redrawn satisfying these assumptions without creating new crossing pairs.
To define our triangulation, around every vertex we draw a small generic triangle such that is disjoint from all curves whose endpoint is not . We can guarantee that any two of these triangles are disjoint, no curve passes through a vertex of , and every curve crosses the boundary of at most once. Additionally, we draw a large triangle enclosing the whole drawing of and all these small triangles. Let be a triangulation of , whose vertices are the vertices of the triangles and , . We call the drawings of the edges of curves, in order to distinguish them from the edges of the triangulation , which are called edges. fig:1 illustrates this construction.
A generic choice of triangles also ensures that no crossing between two curves is contained on an edge of , and no curve touches an edge of . Furthermore, we observe that has vertices, edges, and triangles. The edges of that are adjacent to only one triangle of are the boundary edges, and edges contained in two triangles are the internal edges. Note that every triangle of contains at most one boundary edge.
Before introducing the charging scheme, we justify one further non-degeneracy assumption about how the curves of interact with the triangulation . Namely, we assume that whenever a curve enters a triangle through one of its edges then it cannot immediately leave it again through the same edge. In other words, we show that we can redraw our graph so that no edge of contains consecutive intersection points of a curve. The same statement can be found in [15], but we include a detailed proof for completeness.
Lemma 2.1. The curves of can be redrawn without creating new crossing pairs, such that no curve has two consecutive intersection points with edges of lying on the same edge.
Proof. Let be a triangle of and assume that a curve crosses at points and , such that the part of between and , denoted by , is contained entirely in . The subcurve together with the segment is a closed Jordan curve enclosing a region , called a lune (see Figure 2). Among all lunes in the drawing, choose a lune that is inclusion-minimal. Since lies in a single triangle of , its interior contains no vertex of the drawing.

Figure 2. Removing an inclusion-minimal lune without introducing new crossings.
Replace by a curve running sufficiently close to on the opposite side of from . This removes the two crossings at . We claim that it creates no new crossing pair of curves. Indeed, by choosing sufficiently close to , any curve meeting must cross the interior of . If did not meet , then, upon entering through , it could neither end inside nor leave through . It would therefore have to leave through again. The part of between two successive such crossings would bound, together with a subsegment of , a lune strictly contained in , a contradiction. Thus, we can sequentially destroy inclusion-minimal lunes until none remains without creating new crossing pairs. This proves the lemma.
In the rest of the proof, we fix a drawing of satisfying the conclusion of Lemma 2.1.
Left and right orders
We now slowly move towards defining our charging rule, which charges each curve to at least one of the triangles or edges of it traverses. Formally, we consider orientations of the edges of and write for the ordered pair . Then we can speak of the triangle lying on the left (or right) of a given . A crucial part of the charging scheme is to define, for every , two associated linear orders, the left one and the right one , each over the curves that cross this edge. Since a given curve may intersect multiple times, we consider each such intersection separately. More precisely, let
and define and as linear orders on .
An informal meaning of these orders, which might be helpful to understand the upcoming definition is the following. Assume that the curves and do not intersect in our drawing. Then should mean that on the left of the curve lies below . A key property that we will prove later, and which follows this intuition, is that if the relative orders of and are different on both sides, then the curves and must cross.
Formally, let be an oriented edge of , and let . We first order the pairs and by , and later we argue that this definition indeed gives a linear order.
If is a boundary edge with the only face of on the right side, then if is closer to than .
Otherwise, let be the triangle of to the left of . Walk along the curves and through the triangle , starting from the points and , and continuing until the first intersection with some side of the triangle. Let these intersection points be and , respectively, and note that by the non-degeneracy assumption from Lemma 2.1. We define the relation recursively depending on which of the following cases occurs (see also Figure 3 for an illustration). – If and , then . – If and , then . – If , then and are ordered as orders and . – If , then and are ordered as orders and .

Figure 3. In the first two diagrams, we declare that precedes in , while in the latter two diagrams, we copy the ordering from either or .
The right order is defined analogously, with the only difference being that we consider the triangles to the right of the edge instead of to the left. We observe that left order of is the reverse of the right order of , although we will not make use of this property.
A priori, it is not obvious that the above definitions of and really give us linear orders. To address that, we will now give two alternative definitions of these orders. The first immediately shows that and are indeed linear orders, while the second is meant to give some intuition about how the orders arose in the first place.
The first interpretation is that can be seen as a lexicographic ordering of words defined as follows. Let be an oriented edge, and let . Starting from , start walking along in the left direction of . Every time we enter a triangle along an oriented edge , orient as , and orient as (possibly reorienting previously oriented edges). If leaves the triangle through (informally, “goes down”), we write the letter 0. If it leaves through (informally, “goes up”), we write down the letter 1. If we reach a boundary edge , we write down the distance between and the intersection point of with . This defines a word , whose letters are real numbers (see Figure 4). One can see that corresponds to the lexicographic ordering of these words, so is indeed a linear order. We can treat analogously, but we create a word by traversing in the right direction starting from .

Figure 4. To define the word we walk along from to the left of . We write a 0 when crossing a “lower” edge and a 1 when crossing an “upper” edge. At a boundary edge of we write the distance of the intersection points to the beginning of the edge.
Another way to think about the orders and is through the notion of universal covers. We will not use this perspective in any of the proofs, so we will describe it informally, with the hope that it would give the reader an intuitive understanding of the construction. A universal cover of a topological space is a simply connected topological space with a covering map . For us, the universal cover is an infinite tree of triangles, and we denote it by .
Let be an edge of which projects to and let be the set of all lifts of some curve which have . These correspond to the pairs where is a curve in and . Consider all triangles of encountered by a lift of some edge intersecting , and let their union be . Since is a union of finitely many triangles in the infinite tree and is connected, it is homeomorphic to a disc whose boundary contains and . Therefore, and split the boundary of into two parts. Moreover, the lift of any curve considered above contains a point on both of these. The ordering of the pairs under is then given by the order in which the corresponding lifts meet the part of the boundary of to the left of the edge , when walking from to (and similarly for the order ).
As mentioned earlier, the key property of the linear orders is that if for some pair and their relative orders in and swap, then the curves and must cross. This is expressed in the following lemma.
Lemma 2.2. Let be an oriented edge of the triangulation , and let . If
then crosses .
Proof. Assume to the contrary that and do not cross. We assume that is closer to the start of than , and show that implies that and cross. In case is closer to the start, one can argue similarly that implies that and cross.
Starting from , traverse to the left of , and let be the sequence of oriented edges of the triangulation it meets. Note that is a boundary edge. Similarly, starting from , traverse to the left and let be the sequence of oriented edges of the triangulation crossed by .
Follow the curves and as long as they intersect the same edges. Formally, let be the largest index such that . For , let and be the corresponding intersection points of with and , respectively. Assume that for some , we have that is closer to the start of than . Then for the first such , we have that and cross while traversing from to (see Figure 5(a)). Hence, we can assume that for each , the point is closer to the start of than .
Now note that either the full sequences and are the same, or the curves and separate after . In the first case, and must cross the same boundary edge . But then implies that is closer to the starting point of than , contradiction.
In the second case, let be the triangle to the left of . Since , the curve exits through the edge , while exits it through . However, this also means that and must cross each other (see Figure 5(b)). □

Figure 5. We assumed lies above at , but the definition of implies lies below at an earlier triangle.
Erdős-Szekeres decompositions and the charging scheme.
Recall that our proof of Theorem 1.1 is based on a charging scheme — we charge every curve to at least one oriented edge of triangle of such that no oriented edge or triangle is charged with more than curves. On a high level, the scheme works as follows. At each oriented edge , we assign to each a successor, which is another curve crossing . Then, looking at a curve , we charge it to each triangle at which its successor changes. Since we have no parallel curves in , such a successor change has to happen at some point for each curve . In order to define the notion of a successor, we introduce one further ingredient, which we call the Erdős-Szekeres decomposition.
Let be an abstract set together with two linear orders, and . An increasing subsequence in is a sequence of elements of that is strictly increasing in both and , and a decreasing subsequence is a sequence that is strictly increasing in , but decreasing in . Each such set with orders naturally corresponds to a sequence of distinct real numbers, where orders the numbers by their position in the sequence, while orders the numbers by their size.
In the case of our drawing, at each oriented edge , we consider with the orders and . We note that does not contain a decreasing subsequence of length , since by Lemma 2.2 it would correspond to pairwise crossing curves. The Erdős-Szekeres theorem [9] states that every sequence of distinct real numbers with no decreasing subsequence of length contains an increasing subsequence of length at least . One of the most elegant proofs of this result, which is attributed to Seidenberg [17], also provides a compact method to decompose such a sequence into a union of at most increasing subsequences. This particular decomposition is crucial to our charging scheme and allows us to define the successor of an element.
Definition 2.3. Let be a set and two linear orders on . For every , define
The Erdős-Szekeres decomposition of is the partition of into sets
Each is an increasing sequence in . Given , the successor of in is defined as the successor of in . If is the last element of the sequence, it has no successor. See Figure 6 for an illustration.
Figure 6. The Erdős-Szekeres decomposition and the successors.
It is not hard to see that if contains no decreasing subsequence of length , then the resulting Erdős-Szekeres decomposition consists of at most non-empty sets, since for all . Thus, the Erdős-Szekeres decomposition of is composed of at most non-empty sets. For each pair , we define its successor at as its successor in with respect to the orders and . Now we are ready to define our charging scheme.
Charging scheme. Let be a curve in our drawing.
Let be an oriented edge of . If there is a point such that has no successor at the edge , then charge to . In this case, we say that has no successor at .
Let be a triangle of , and assume that crosses and in consecutive points and . Then charge to if – the successor of at and the successor of at come from different curves, – the successor of at and the successor of at come from different curves.
If is charged to , we say that switches successors in .
We now argue that every curve is charged to at least one oriented edge or triangle, and that no oriented edge or triangle is charged with too many curves.
Lemma 2.4. Every curve is charged to at least one oriented edge or triangle of .
Proof. Traverse from one endpoint to the other, and let be the sequence of edges of crossed by in order, and let be the corresponding crossing points. Note that and are boundary edges. Orient each edge as such that crosses from right-to-left.
Assume that has a successor at every edge , as otherwise is charged to some oriented edge. Moreover, if for some , the successors of at and at come from different curves, then is charged to the triangle whose sides are and .
So, if is not charged at any step, its successor at both boundary edges and must correspond to the same curve, say . But then and are parallel edges in the graph , contradicting the fact that is a simple graph. □
The final step of the proof is showing that at most curves are charged to any given triangle, and curves are charged to any edge. To this end, we wish to understand how the Erdős-Szekeres decompositions for two oriented edges, say and , of the same triangle differ.
Let be a set with linear orders and let be its subset, ordered with the same linear orders. Define
If an element has no successor in , but has one in , it is also included in . Similarly, if has no successor in , but has one in , it is also included. The following lemma bounds the maximum number of successor changes that may occur if we restrict to certain special subsets of , see Figure 7 for an illustration.
Figure 7. An illustration of the Erdős-Szekeres decompositions of and in case (1), where the red points denote the elements of . The circled elements have different successors in and .
Lemma 2.5. Let , and let be two linear orders on , such that there is no decreasing sequence of length in .
(1) Assume is the set of smallest elements in under . Then .
(2) Assume is the set of largest elements in under . Then .
(3) Assume is the set of first elements in under . Then .
(4) Assume is the set of last elements in under . Then .
We postpone the proof of Lemma 2.5 to the next subsection. Here, we finish the analysis of our charging scheme, by showing that each oriented edge and triangle is charged with at most curves.
Lemma 2.6. (a) An oriented edge of is charged with at most curves.
(b) A triangle of is charged with at most curves.
Proof. (a) The oriented edge is charged with if there is some such that is the largest element of one of the increasing sequences given by the Erdős-Szekeres decomposition. There are at most sequences in this decomposition, so this finishes the proof.
(b) Recall that is charged with a curve if for some
the curve crosses and in some consecutive points and , respectively, such that the successor of at comes from a different curve than the successor of at . It suffices to show that a triangle is charged with at most curves for each of the six listed pairs. By symmetry, it suffices to analyze only two cases, namely when and (see Figure 8).

Figure 8. The two cases in the proof of Lemma 2.6(b). The set consists of highlighted curves, which connect to . The orders of and agree on .
First, let , and assume that the triangle is to the left of , as otherwise we can switch and . Let be the set of triples for which the curve joins the points and without exiting the triangle . Then can be naturally identified with subsets of both and .
Our goal is now to count the number of triples for which the successors of at and at come from different curves. From their definition, we see that the orders agree with on . Under this identifications, the successors in the decomposition of on the two edges agree.
Note that is the set of first elements in under (this is illustrated in Figure 8, since the edges of have the left endpoint “below” the other curves intersecting ). Hence, (3) in Lemma 2.5 implies that . Similarly, is the set of smallest elements in under , and so (1) in Lemma 2.5 implies that . Thus, the number of elements of with different successors in and is at most .
The argument proceeds very similarly when . Assuming now that is to the left of , we define as before, and observe that it is a subset of both and . In this case, is the set of last elements in under , and therefore (4) in Lemma 2.5 implies that . On the other hand, is also the set of largest elements in under , and therefore (2) in Lemma 2.5 shows that . This is illustrated in Figure 8(b). Hence, the number of elements of with different successors in and is at most .
Combining Lemma 2.4 with Lemma 2.6 immediately implies Theorem 1.1.
Bounding the number of successor changes
The only remaining bit is hence to prove Lemma 2.5. The proof is slightly technical, but the main idea is to simply look at how the lengths of the longest decreasing sequences and can differ in each of the cases.
Proof of Lemma 2.5. We consider the four cases individually. Recall that for , denotes the length of the longest decreasing sequence in ending with . Throughout the proof, we think of as sequences, where comes before if .
(1) We begin with two preparatory claims. First, we claim that if comes before in and both belong to the same increasing sequence in the decomposition of , i.e. , then .
Assume for contradiction that there exist violating this statement. Among all such pairs , choose one that minimizes . Let be a decreasing subsequence of of length ending at . Note that if all elements of are in , then replacing by in the sequence yields a decreasing subsequence of length ending at , giving . Let be the element of preceding , then . If , then replacing with in would again yield a decreasing subsequence of length , so we must have . Moreover, . Let be such that and lies on a decreasing subsequence of length ending at in . As , we have . By the minimality of , we must have , and hence , a contradiction.
Next, we state and prove our second claim. It states that if comes before in and , then .
Assume for contradiction that for some preceding in , we have and . Consider a decreasing subsequence of of length ending at , and let be an element of this sequence such that . We have , and thus lies between and in the sequence. Then, by the previous claim, we get , and therefore , a contradiction.
Consider , i.e. the increasing sequences in the decomposition of composed of elements such that . Let be the elements of which have different successors in and . We claim that
The first of these inequalities follows since , while the last one follows since contains no decreasing subsequence of length .
Hence, it remains to prove that for , we have . Let be the successor of in . By the first claim applied to the pairs and (noting that both pairs satisfy the assumptions of the claim by definition), we have , so it suffices to show that .
Suppose we had . If is the successor of in , then is between and in the sequence and has . So, and are in the same increasing sequence of , and we would have . As is the set of smallest elements under , this implies . Applying the second claim to the pairs and then shows that and . As , this quantity equals , which means that is in the same increasing sequence of as and . But then cannot be the successor of in , contradiction.
We proved that in , there are elements whose successor is changed. Thus, the statement of (1) is then immediately obtained by summing over , i.e. .
(2) Clearly, we have for all as no decreasing subsequence ending at can contain an element from . Moreover, for every and such that precedes , we have , as we can append to every decreasing subsequence ending at . This implies that all have the same successor in both and .
(3) As in the previous case, we have for all as these value do not depend on elements for which precedes . It immediately follows that every that has a successor in has the same successor in . Only the elements of with no successor in can gain a successor in , showing that .
(4) We show that (1) implies (4) by a symmetry argument.
Let be the reverse of , and let be the reverse of on . To minimize confusion, we denote by the sets when they are ordered using the orders . Observe that reversing an increasing sequence with respect to gives an increasing sequence in . On the other hand, a decreasing sequence with respect to orders remains decreasing with respect to orders . In particular, for every element , the length of the longest decreasing sequence ending at is unchanged, i.e. and . Hence, the successor of in (or ) is the predecessor of in (or ). The predecessor of is the element immediately before it in its increasing sequence in the Erdős-Szekeres decomposition.
The main advantage of this transformation is that is now the set of smallest elements in under , which corresponds to the situation of (1). To bound , we bound the number of elements with different predecessors in and . If the starting elements of the increasing sequences are the same in and , then the number of whose predecessor changes is at most (which is at most by (1)). The reason is simple: if was the predecessor of in , but is not in , then the successor of must have changed from to .
To ensure that the increasing sequences in both and start with the same elements, add to the start of both sequences a set consisting of dummy elements with and , such that and for all . A dummy and a real element cannot be in the same decreasing sequence, and so the increasing sequences in both and start with . Therefore, , where the last inequality follows from (1), since is the set of smallest elements in under .
AI declaration
The AI tools were used for understanding the paper of Beeker and Lazarovich [5]. The main new idea of this work, to consider the orders and the resulting Erdős-Szekeres decomposition is due to the authors. Once provided with this idea and the statement of Lemma 2.5, AI tools assisted in the proof of Lemma 2.5.
References
References
- [1]E. Ackerman. On the maximum number of edges in topological graphs with no four pairwise crossing edges. Discrete Comput. Geom. 41 (2009): 365–375.
- [2]E. Ackerman, and G. Tardos. On the maximum number of edges in quasi-planar graphs. J. Combin. Theory Ser. A 114(3) (2007): 563–571.DOI
- [3]P. K. Agarwal, B. Aronov, J. Pach, R. Pollack and M. Sharir. Quasi-planar graphs have a linear number of edges. Combinatorica 17 (1997): 1–9.
- [4]B. Aronov, P. Erdős, W. Goddard, D.J. Kleitman, M. Klugerman, J. Pach, and L.J. Schulman. Crossing families. Combinatorica 14 (2) (1994): 127–134.
- [5]B. Beeker, and N. Lazarovich. Cubical accessibility and bounds on curves on surfaces. Journal of Topology 10 (2017): 1050–1065.DOI
- [6]J. F. Brandenburg. A simple quasi-planar drawing of K₁₀. In Graph Drawing, vol. 9801 (2016): 603–604.
- [7]P. Brass, W. Moser, and J. Pach. Research Problems in Discrete Geometry. Berlin, Germany, Springer-Verlag, 2005.DOI
- [8]V. Capoyleas, and J. Pach. A Turán-type theorem on chords of a convex polygon. J. Comb. Theory Ser. B 56 (1992): 9–15.DOI
- [9]P. Erdős, and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica 2 (1935): 463–470.
- [10]I. Fáry. On straight-line representation of planar graphs Acta Sci. Math. (Szeged), 11 (1948): 229–233.
- [11]J. Fox, and J. Pach. Applications of a new separator theorem for string graphs. Combin. Probab. Comput. 23 (2014): 66–74.arxiv.org/abs/1302.7228
- [12]J. Fox, J. Pach, and A. Suk. Quasiplanar graphs, string graphs, and the Erdős–Gallai problem. European Journal of Combinatorics 119 (2024): 103811.arxiv.org/abs/2112.02378
- [13]J. Pach, N. Rubin, and G. Tardos. Planar point sets determine many pairwise crossing segments. Advances in Mathematics 386 (2021): 107779.
- [14]J. Pach, F. Shahrokhi, and M. Szegedy. Applications of the crossing number. J. Graph Theory 22 (1996): 239–243.
- [15]J. Pach, G. Tardos, and J. Zeng. On the number of edges in quasiplanar graphs. preprint, arXiv:2611.07314 (2026)arxiv.org/abs/2611.07314
- [16]A. Sadhu. Every k-Quasi-Planar Graph Has Linearly Many Edges. preprint, arXiv:2611.01509 (2026)
- [17]A. Seidenberg. A simple proof of a theorem of Erdős and Szekeres. Journal of the London Mathematical Society, 34 (3) (1959): 352.DOI
- [18]G. Tóth. Note on Geometric Graphs. Journal of Combinatorial Theory, Series A 89 (2000): 126–132.DOI
- [19]P. Valtr. Graph drawing with no k pairwise crossing edges. International Symposium on Graph Drawing. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997.DOI
- [20]P. Valtr. On geometric graphs with no k pairwise parallel edges. Discrete Comput. Geom. 19 (1998): 461–469.DOI

