betaFeedback

WorksMathematics

Polynomial bounds for quasiplanar graphs

Abstract

A graph GG is kk-quasiplanar if it can be drawn in the plane without kk pairwise crossing edges. It was a longstanding conjecture that nn-vertex kk-quasiplanar graphs have Ok(n)O_k(n) 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 kk-quasiplanar graphs have at most kO(k)nk^{O(k)}n edges. In this note, we greatly improve the dependence on kk and show that every kk-quasiplanar nn-vertex graph has at most O(k2n)O(k^2n) edges. The proof is based on a geometric charging scheme and Erdős-Szekeres type combinatorial arguments.

Introduction

A graph GG 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 nn-vertex planar graph is at most 3n−63n - 6, 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 GG is kk-quasiplanar if it can be drawn in the plane such that no kk edges pairwise cross. Compared to planarity, which corresponds to the case k=2k = 2, kk-quasiplanarity is much less understood for k≥3k \ge3. The difficulty of this notion stems from the fact that 33-quasiplanar graphs can already exhibit strange behavior. For example, Brandenburg [6] showed that the complete graph K10K_{10} is 33-quasiplanar, however, it has no 33-quasiplanar drawing with straight line segments. Furthermore, Ackerman and Tardos [2] showed that there exist 33-quasiplanar graphs such that in every 33-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 nn-vertex kk-quasiplanar graph?

In 1996, Pach, Shahrokhi, and Szegedy [14] conjectured that for every fixed kk, this maximum is Ok(n)O_k(n), and this conjecture was later reiterated by Brass, Moser and Pach [7]. The lack of very dense constructions of kk-quasiplanar graphs led to an even more ambitious folklore conjecture that the above maximum is O(kn)O(kn). 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 k=3k=3 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 7n−O(1)7n-O(1) and 8n−208n-20. The k=4k=4 case was then confirmed by Ackerman [1] in 2009. In general, the quasi-linear upper bound O(n(log⁡n)2k−4)O(n(\log n)^{2k-4}) was proved by Pach, Shahrokhi, and Szegedy [14], which was later improved to n(log⁡n)O(log⁡k)n(\log n)^{O(\log k)} by Fox and Pach [11]. Until recently, the best known bound n(log⁡n/log⁡k)O(log⁡k)n(\log n/\log k)^{O(\log k)} was due to Fox, Pach, and Suk [12]. A notable corollary of this result is that if GG is an nn-vertex graph with at least n1+δn^{1+\delta} edges, then any drawing of GG contains at least nεn^\varepsilon pairwise crossing edges for some ε=ε(δ)>0\varepsilon=\varepsilon(\delta)>0.

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 2(k−1)n−(2k−12)2(k-1)n-\binom{2k-1}{2}. In the less restricted case, when the edges are straight-line segments or xx-monotone curves (and there is no assumption on the vertices), Valtr [19, 20] proved the bound Ok(nlog⁡n)O_k(n\log n). Furthermore, the sharper bound O(k2nlog⁡n)O(k^2n\log n) for straight line drawings follows from a work of Tóth [18].

The linear upper bound Ok(n)O_k(n) for the maximum number of edges of kk-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 k(2+o(1))knk^{(2+o(1))k}n is also established in [15], where the authors note that the dependence on kk is unlikely to be sharp.

Building on these recent works, we greatly improve the dependence on kk, and show the upper bound O(k2n)O(k^2n). This quantitatively improves all previous results for sufficiently large k=k(n)k=k(n), 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 O(k2n)O(k^2n) bound.

Theorem 1.1. Let GG be a kk-quasiplanar nn-vertex graph. Then GG has at most O(k2n)O(k^2n) 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 KnK_n? Aronov, Erdős, Goddard, Kleitman, Klugerman, Pach, and Schulman [4] proved in 1991 that every such drawing contains at least Ω(n)\Omega(\sqrt{n}) pairwise crossing edges, while it is conjectured (see e.g. [7]) that the answer should be Ω(n)\Omega(n). The currently best known lower bound n1−o(1)n^{1-o(1)} 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 KnK_n. This problem is even less understood, and there is no known drawing of KnK_n with fewer than linearly many pairwise crossing edges. The aforementioned result of Fox, Pach and Suk [12] gives a lower bound of nΩ(1)n^{\Omega(1)}. An immediate corollary of Theorem 1.1 sharpens this to Ω(n1/2)\Omega(n^{1/2}) by taking k=cn1/2k=cn^{1/2} for a small constant cc.

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 GG in which no kk 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 O(n)O(n) triangles. Each curve corresponding to an edge of GG starts at a vertex, traverses some triangles of this triangulation and finishes at another vertex of GG. 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 kk edges pairwise cross, we show that the number of curves that are charged to any given edge or triangle is at most O(k2)O(k^2). This immediately implies that the number of edges of GG is at most O(k2)O(k^2) times the number of triangles in our triangulation, i.e., O(k2n)O(k^2n).

Setup.

Formally, let GG be an nn-vertex kk-quasiplanar graph and fix a drawing of GG in which no kk edges pairwise cross. We identify the vertices of GG with the corresponding points in the plane, and the edges of GG with continuous curves, i.e., the images of continuous functions ϕ:[0,1]→R2\phi: [0,1] \to\mathbb{R}^2. 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 v∈V(G)v \in V(G) we draw a small generic triangle TvT_v such that TvT_v is disjoint from all curves whose endpoint is not vv. We can guarantee that any two of these triangles are disjoint, no curve passes through a vertex of TvT_v, and every curve crosses the boundary of TvT_v at most once. Additionally, we draw a large triangle T0T_0 enclosing the whole drawing of GG and all these small triangles. Let T\mathcal{T} be a triangulation of T0∖⋃v∈V(G)TvT_0 \setminus\bigcup_{v \in V(G)} T_v, whose vertices are the vertices of the triangles T0T_0 and TvT_v, v∈V(G)v \in V(G). We call the drawings of the edges of GG curves, in order to distinguish them from the edges of the triangulation T\mathcal{T}, 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 T\mathcal{T}, and no curve touches an edge of T\mathcal{T}. Furthermore, we observe that T\mathcal{T} has 3n+33n+3 vertices, 9n+3=O(n)9n+3 = O(n) edges, and 5n+1=O(n)5n+1 = O(n) triangles. The edges of T\mathcal{T} that are adjacent to only one triangle of T\mathcal{T} are the boundary edges, and edges contained in two triangles are the internal edges. Note that every triangle of T\mathcal{T} contains at most one boundary edge.

Before introducing the charging scheme, we justify one further non-degeneracy assumption about how the curves of GG interact with the triangulation T\mathcal{T}. 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 T\mathcal{T} 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 GG can be redrawn without creating new crossing pairs, such that no curve α\alpha has two consecutive intersection points with edges of T\mathcal{T} lying on the same edge.

Proof. Let xyzxyz be a triangle of T\mathcal{T} and assume that a curve α\alpha crosses xyxy at points aa and bb, such that the part of α\alpha between aa and bb, denoted by α0\alpha_0, is contained entirely in xyzxyz. The subcurve α0\alpha_0 together with the segment abab is a closed Jordan curve enclosing a region LL, called a lune (see Figure 2). Among all lunes in the drawing, choose a lune LL that is inclusion-minimal. Since LL lies in a single triangle xyzxyz of T\mathcal{T}, its interior contains no vertex of the drawing.

Removing an inclusion-minimal lune without introducing new crossings

Figure 2. Removing an inclusion-minimal lune without introducing new crossings.

Replace α\alpha by a curve α′\alpha' running sufficiently close to abab on the opposite side of xyxy from LL. This removes the two crossings at a,ba,b. We claim that it creates no new crossing pair of curves. Indeed, by choosing α′\alpha' sufficiently close to abab, any curve β\beta meeting α′\alpha' must cross the interior of abab. If β\beta did not meet α\alpha, then, upon entering LL through abab, it could neither end inside LL nor leave through α\alpha. It would therefore have to leave through abab again. The part of β\beta between two successive such crossings would bound, together with a subsegment of abab, a lune strictly contained in LL, 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 GG 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 TT it traverses. Formally, we consider orientations of the edges of TT and write xy→\overrightarrow{xy} for the ordered pair (x,y)(x,y). Then we can speak of the triangle lying on the left (or right) of a given xy→\overrightarrow{xy}. A crucial part of the charging scheme is to define, for every xy→\overrightarrow{xy}, two associated linear orders, the left one ≺L\prec_L and the right one ≺R\prec_R, each over the curves that cross this edge. Since a given curve α\alpha may intersect xyxy multiple times, we consider each such intersection separately. More precisely, let

Cxy={(α,p):α is a curve intersecting xy in point p},C_{xy}=\{(\alpha,p): \alpha\text{ is a curve intersecting }xy\text{ in point }p\},

and define ≺L\prec_L and ≺R\prec_R as linear orders on CxyC_{xy}.

An informal meaning of these orders, which might be helpful to understand the upcoming definition is the following. Assume that the curves α\alpha and β\beta do not intersect in our drawing. Then (α,p)≺L(β,q)(\alpha,p)\prec_L(\beta,q) should mean that on the left of xy→\overrightarrow{xy} the curve α\alpha lies below β\beta. A key property that we will prove later, and which follows this intuition, is that if the relative orders of (α,p)(\alpha,p) and (β,q)(\beta,q) are different on both sides, then the curves α\alpha and β\beta must cross.

Formally, let xy→\overrightarrow{xy} be an oriented edge of TT, and let (α,p),(β,q)∈Cxy(\alpha,p),(\beta,q)\in C_{xy}. We first order the pairs (α,p)(\alpha,p) and (β,q)(\beta,q) by ≺L=≺Lxy\prec_L=\prec_L^{xy}, and later we argue that this definition indeed gives a linear order.

  • If xyxy is a boundary edge with the only face of TT on the right side, then (α,p)≺L(β,q)(\alpha,p)\prec_L(\beta,q) if pp is closer to xx than qq.

  • Otherwise, let xyzxyz be the triangle of TT to the left of xy→\overrightarrow{xy}. Walk along the curves α\alpha and β\beta through the triangle xyzxyz, starting from the points pp and qq, and continuing until the first intersection with some side of the triangle. Let these intersection points be p′p' and q′q', respectively, and note that p′,q′∈xz∪zyp',q'\in xz\cup zy by the non-degeneracy assumption from Lemma 2.1. We define the relation ≺L\prec_L recursively depending on which of the following cases occurs (see also Figure 3 for an illustration). – If p′∈xzp'\in xz and q′∈zyq'\in zy, then (α,p)≺L(β,q)(\alpha,p)\prec_L(\beta,q). – If p′∈zyp'\in zy and q′∈xzq'\in xz, then (β,q)≺L(α,p)(\beta,q)\prec_L(\alpha,p). – If p′,q′∈xzp',q'\in xz, then (α,p)(\alpha,p) and (β,q)(\beta,q) are ordered as ≺Lxz\prec_L^{xz} orders (α,p′)(\alpha,p') and (β,q′)(\beta,q'). – If p′,q′∈zyp',q'\in zy, then (α,p)(\alpha,p) and (β,q)(\beta,q) are ordered as ≺Lzy\prec_L^{zy} orders (α,p′)(\alpha,p') and (β,q′)(\beta,q').

Four diagrams illustrating boundary edge, different exits, same exit xz, and same exit zy

Figure 3. In the first two diagrams, we declare that (α,p)(\alpha,p) precedes (β,q)(\beta,q) in ≺Lxy\prec_L^{xy}, while in the latter two diagrams, we copy the ordering from either ≺Lxz\prec_L^{xz} or ≺Lzy\prec_L^{zy}.

The right order ≺R\prec_R is defined analogously, with the only difference being that we consider the triangles to the right of the edge xy→\overrightarrow{xy} instead of to the left. We observe that left order of xy→\overrightarrow{xy} is the reverse of the right order of yx→\overrightarrow{yx}, although we will not make use of this property.

A priori, it is not obvious that the above definitions of ≺Lxy\prec_L^{xy} and ≺Rxy\prec_R^{xy} really give us linear orders. To address that, we will now give two alternative definitions of these orders. The first immediately shows that ≺Lxy\prec_L^{xy} and ≺Rxy\prec_R^{xy} 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 ≺Lxy\prec_L^{xy} can be seen as a lexicographic ordering of words defined as follows. Let xy→\overrightarrow{xy} be an oriented edge, and let (α,p)∈Cxy(\alpha,p)\in C_{xy}. Starting from pp, start walking along α\alpha in the left direction of xy→\overrightarrow{xy}. Every time we enter a triangle x0y0z0x_0y_0z_0 along an oriented edge x0y0→\overrightarrow{x_0y_0}, orient x0z0→\overrightarrow{x_0z_0} as x0z0→\overrightarrow{x_0z_0}, and orient z0y0→\overrightarrow{z_0y_0} as z0y0→\overrightarrow{z_0y_0} (possibly reorienting previously oriented edges). If α\alpha leaves the triangle x0y0z0x_0y_0z_0 through x0z0x_0z_0 (informally, “goes down”), we write the letter 0. If it leaves through z0y0z_0y_0 (informally, “goes up”), we write down the letter 1. If we reach a boundary edge x0y0→\overrightarrow{x_0y_0}, we write down the distance between x0x_0 and the intersection point of α\alpha with x0y0x_0y_0. This defines a word wα,pLw^L_{\alpha,p}, whose letters are real numbers (see Figure 4). One can see that ≺Lxy\prec_L^{xy} corresponds to the lexicographic ordering of these words, so ≺Lxy\prec_L^{xy} is indeed a linear order. We can treat ≺Rxy\prec_R^{xy} analogously, but we create a word wα,pRw^R_{\alpha,p} by traversing α\alpha in the right direction starting from pp.

A triangulated universal-cover-like diagram showing a curve traversing triangles

Figure 4. To define the word wα,pLw^L_{\alpha,p} we walk along α\alpha from pp to the left of xy→\overrightarrow{xy}. We write a 0 when crossing a “lower” edge and a 1 when crossing an “upper” edge. At a boundary edge of TT we write the distance of the intersection points to the beginning of the edge.

Another way to think about the orders ≺L\prec_L and ≺R\prec_R 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 XX is a simply connected topological space X~\widetilde{X} with a covering map π:X~→X\pi:\widetilde{X}\to X. For us, the universal cover is an infinite tree of triangles, and we denote it by T~\widetilde{T}.

Let ee be an edge of T~\widetilde{T} which projects to xyxy and let LL be the set of all lifts α~\widetilde{\alpha} of some curve α\alpha which have α~∩e≠∅\widetilde{\alpha}\cap e\ne\varnothing. These correspond to the pairs (α,p)(\alpha,p) where α\alpha is a curve in TT and p∈xy∩αp\in xy\cap\alpha. Consider all triangles of T~\widetilde{T} encountered by a lift of some edge intersecting ee, and let their union be DD. Since DD is a union of finitely many triangles in the infinite tree T~\widetilde{T} and is connected, it is homeomorphic to a disc whose boundary contains xx and yy. Therefore, xx and yy split the boundary of DD into two parts. Moreover, the lift of any curve α\alpha considered above contains a point on both of these. The ordering of the pairs (α,p)(\alpha,p) under ≺L\prec_L is then given by the order in which the corresponding lifts meet the part of the boundary of DD to the left of the edge xy→\overrightarrow{xy}, when walking from xx to yy (and similarly for the order ≺R\prec_R).

As mentioned earlier, the key property of the linear orders is that if for some pair (α,p)(\alpha,p) and (β,q)(\beta,q) their relative orders in ≺L\prec_L and ≺R\prec_R swap, then the curves α\alpha and β\beta must cross. This is expressed in the following lemma.

Lemma 2.2. Let e⃗\vec{e} be an oriented edge of the triangulation TT, and let (α,p),(β,q)∈Ce(\alpha,p),(\beta,q) \in C_e. If

(β,q)≺Le(α,p)and(α,p)≺Re(β,q),(\beta,q) \prec_L^e (\alpha,p) \qquad\text{and}\qquad(\alpha,p) \prec_R^e (\beta,q),

then α\alpha crosses β\beta.

Proof. Assume to the contrary that α\alpha and β\beta do not cross. We assume that pp is closer to the start of ee than qq, and show that (β,q)≺Le(α,p)(\beta,q) \prec_L^e (\alpha,p) implies that α\alpha and β\beta cross. In case qq is closer to the start, one can argue similarly that (α,p)≺Re(β,q)(\alpha,p) \prec_R^e (\beta,q) implies that α\alpha and β\beta cross.

Starting from pp, traverse α\alpha to the left of e⃗\vec{e}, and let e⃗=e⃗1,e⃗2,…,e⃗r\vec{e}=\vec{e}_1,\vec{e}_2,\ldots,\vec{e}_r be the sequence of oriented edges of the triangulation it meets. Note that e⃗r\vec{e}_r is a boundary edge. Similarly, starting from qq, traverse β\beta to the left and let e⃗=f⃗1,f⃗2,…,f⃗s\vec{e}=\vec{f}_1,\vec{f}_2,\ldots,\vec{f}_s be the sequence of oriented edges of the triangulation crossed by β\beta.

Follow the curves α\alpha and β\beta as long as they intersect the same edges. Formally, let II be the largest index such that e1=f1,…,eI=fIe_1=f_1,\ldots,e_I=f_I. For i=1,…,Ii=1,\ldots,I, let pip_i and qiq_i be the corresponding intersection points of ei=fie_i=f_i with α\alpha and β\beta, respectively. Assume that for some i≥2i\ge2, we have that qiq_i is closer to the start of e⃗i\vec{e}_i than pip_i. Then for the first such ii, we have that α\alpha and β\beta cross while traversing from ei−1e_{i-1} to eie_i (see Figure 5(a)). Hence, we can assume that for each i≤Ii\le I, the point pip_i is closer to the start of e⃗i\vec{e}_i than qiq_i.

Now note that either the full sequences e1,…,ere_1,\ldots,e_r and f1,…,fsf_1,\ldots,f_s are the same, or the curves α\alpha and β\beta separate after eI=fIe_I=f_I. In the first case, α\alpha and β\beta must cross the same boundary edge ese_s. But then (β,q)≺Le(α,p)(\beta,q) \prec_L^e (\alpha,p) implies that qsq_s is closer to the starting point of e⃗s\vec{e}_s than psp_s, contradiction.

In the second case, let xyzxyz be the triangle to the left of e⃗I=xy⃗\vec{e}_I=\vec{xy}. Since (β,q)≺Le(α,p)(\beta,q) \prec_L^e (\alpha,p), the curve β\beta exits xyzxyz through the edge xz⃗\vec{xz}, while α\alpha exits it through zy⃗\vec{zy}. However, this also means that α\alpha and β\beta must cross each other (see Figure 5(b)). □

Two configurations showing crossings of curves alpha and beta

Figure 5. We assumed β\beta lies above α\alpha at xy⃗\vec{xy}, but the definition of ≺L\prec_L implies β\beta lies below α\alpha 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 TT such that no oriented edge or triangle is charged with more than O(k2)O(k^2) curves. On a high level, the scheme works as follows. At each oriented edge xy⃗\vec{xy}, we assign to each (α,p)∈Cxy(\alpha,p)\in C_{xy} a successor, which is another curve β\beta crossing xyxy. Then, looking at a curve α\alpha, we charge it to each triangle at which its successor changes. Since we have no parallel curves in GG, such a successor change has to happen at some point for each curve α\alpha. In order to define the notion of a successor, we introduce one further ingredient, which we call the Erdős-Szekeres decomposition.

Let SS be an abstract set together with two linear orders, ≺L\prec_L and ≺R\prec_R. An increasing subsequence in SS is a sequence of elements of SS that is strictly increasing in both ≺L\prec_L and ≺R\prec_R, and a decreasing subsequence is a sequence that is strictly increasing in ≺L\prec_L, but decreasing in ≺R\prec_R. Each such set SS with orders ≺L,≺R\prec_L,\prec_R naturally corresponds to a sequence of distinct real numbers, where ≺L\prec_L orders the numbers by their position in the sequence, while ≺R\prec_R orders the numbers by their size.

In the case of our drawing, at each oriented edge xy→\overrightarrow{xy}, we consider CxyC_{xy} with the orders ≺Lxy\prec_L^{xy} and ≺Rxy\prec_R^{xy}. We note that CxyC_{xy} does not contain a decreasing subsequence of length kk, since by Lemma 2.2 it would correspond to kk pairwise crossing curves. The Erdős-Szekeres theorem [9] states that every sequence of nn distinct real numbers with no decreasing subsequence of length kk contains an increasing subsequence of length at least n/(k−1)n/(k-1). 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 k−1k-1 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 SS be a set and ≺L,≺R\prec_L,\prec_R two linear orders on SS. For every x∈Sx \in S, define

ℓS(x)=length of the longest decreasing subsequence ending with x.\ell_S(x) = \text{length of the longest decreasing subsequence ending with }x.

The Erdős-Szekeres decomposition of SS is the partition of SS into sets

LS(i)={x∈S:ℓS(x)=i}for i=1,2,….L_S(i)=\{x\in S:\ell_S(x)=i\}\quad\text{for }i=1,2,\ldots.

Each LS(i)L_S(i) is an increasing sequence in SS. Given x∈LS(i)x\in L_S(i), the successor of xx in SS is defined as the successor of xx in LS(i)L_S(i). If xx 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 SS contains no decreasing subsequence of length kk, then the resulting Erdős-Szekeres decomposition consists of at most k−1k-1 non-empty sets, since ℓS(x)≤k−1\ell_S(x)\leq k-1 for all x∈Sx\in S. Thus, the Erdős-Szekeres decomposition of CxyC_{xy} is composed of at most k−1k-1 non-empty sets. For each pair (α,p)(\alpha,p), we define its successor at xy→\overrightarrow{xy} as its successor in CxyC_{xy} with respect to the orders ≺Lxy\prec_L^{xy} and ≺Rxy\prec_R^{xy}. Now we are ready to define our charging scheme.

Charging scheme. Let α\alpha be a curve in our drawing.

  • Let xy→\overrightarrow{xy} be an oriented edge of TT. If there is a point p∈α∩xyp\in\alpha\cap xy such that (α,p)(\alpha,p) has no successor at the edge xy→\overrightarrow{xy}, then charge α\alpha to xy→\overrightarrow{xy}. In this case, we say that α\alpha has no successor at xy→\overrightarrow{xy}.

  • Let xyzxyz be a triangle of TT, and assume that α\alpha crosses xyxy and xzxz in consecutive points pp and qq. Then charge α\alpha to xyzxyz if – the successor of (α,p)(\alpha,p) at xy→\overrightarrow{xy} and the successor of (α,q)(\alpha,q) at xz→\overrightarrow{xz} come from different curves, – the successor of (α,p)(\alpha,p) at yx→\overrightarrow{yx} and the successor of (α,q)(\alpha,q) at zx→\overrightarrow{zx} come from different curves.

If α\alpha is charged to xyzxyz, we say that α\alpha switches successors in xyzxyz.

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 α\alpha is charged to at least one oriented edge or triangle of TT.

Proof. Traverse α\alpha from one endpoint to the other, and let e1,…,ese_1,\ldots,e_s be the sequence of edges of TT crossed by α\alpha in order, and let p1,…,psp_1,\ldots,p_s be the corresponding crossing points. Note that e1e_1 and ese_s are boundary edges. Orient each edge eie_i as ei→\overrightarrow{e_i} such that α\alpha crosses from right-to-left.

Assume that (α,pi)(\alpha,p_i) has a successor at every edge eie_i, as otherwise α\alpha is charged to some oriented edge. Moreover, if for some ii, the successors of (α,pi)(\alpha,p_i) at eie_i and (α,pi+1)(\alpha,p_{i+1}) at ei+1e_{i+1} come from different curves, then α\alpha is charged to the triangle whose sides are eie_i and ei+1e_{i+1}.

So, if α\alpha is not charged at any step, its successor at both boundary edges e1e_1 and ese_s must correspond to the same curve, say β\beta. But then α\alpha and β\beta are parallel edges in the graph GG, contradicting the fact that GG is a simple graph. □

The final step of the proof is showing that at most O(k2)O(k^2) curves are charged to any given triangle, and O(k)O(k) curves are charged to any edge. To this end, we wish to understand how the Erdős-Szekeres decompositions for two oriented edges, say xy→\overrightarrow{xy} and xz→\overrightarrow{xz}, of the same triangle differ.

Let S′S' be a set with linear orders ≺L,≺R\prec_L, \prec_R and let S⊆S′S \subseteq S' be its subset, ordered with the same linear orders. Define

D(S,S′)=#{x∈S: the successor of x in S is different from its successor in S′}.\mathcal{D}(S,S')=\#\{x\in S:\text{ the successor of }x\text{ in }S\text{ is different from its successor in }S'\}.

If an element xx has no successor in SS, but has one in S′S', it is also included in D(S,S′)\mathcal{D}(S,S'). Similarly, if xx has no successor in S′S', but has one in SS, 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 S′S', see Figure 7 for an illustration.

Figure 7. An illustration of the Erdős-Szekeres decompositions of SS and S′S' in case (1), where the red points denote the elements of SS. The circled elements have different successors in SS and S′S'.

Lemma 2.5. Let S⊆S′S\subseteq S', and let ≺L,≺R\prec_L,\prec_R be two linear orders on S′S', such that there is no decreasing sequence of length kk in S′S'.

(1) Assume SS is the set of ∣S∣|S| smallest elements in S′S' under ≺R\prec_R. Then D(S,S′)≤(k2)\mathcal{D}(S,S')\leq\binom{k}{2}.

(2) Assume SS is the set of ∣S∣|S| largest elements in S′S' under ≺R\prec_R. Then D(S,S′)=0\mathcal{D}(S,S')=0.

(3) Assume SS is the set of first ∣S∣|S| elements in S′S' under ≺L\prec_L. Then D(S,S′)≤k−1\mathcal{D}(S,S')\leq k-1.

(4) Assume SS is the set of last ∣S∣|S| elements in S′S' under ≺L\prec_L. Then D(S,S′)≤(k2)\mathcal{D}(S,S')\leq\binom{k}{2}.

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 O(k2)O(k^2) curves.

Lemma 2.6. (a) An oriented edge xy→\overrightarrow{xy} of TT is charged with at most k−1k-1 curves.

(b) A triangle xyzxyz of TT is charged with at most 6k26k^2 curves.

Proof. (a) The oriented edge xy→\overrightarrow{xy} is charged with α\alpha if there is some p∈α∩xyp\in\alpha\cap xy such that (α,p)(\alpha,p) is the largest element of one of the increasing sequences given by the Erdős-Szekeres decomposition. There are at most k−1k-1 sequences in this decomposition, so this finishes the proof.

(b) Recall that xyzxyz is charged with a curve α\alpha if for some

(e,f)∈{(xy,xz),(yx,zx),(yx,yz),(xy,zy),(xz,yz),(zx,zy)}(e,f)\in\{(xy,xz),(yx,zx),(yx,yz),(xy,zy),(xz,yz),(zx,zy)\}

the curve α\alpha crosses ee and ff in some consecutive points pp and qq, respectively, such that the successor of (α,p)(\alpha,p) at e⃗\vec{e} comes from a different curve than the successor of (α,q)(\alpha,q) at f⃗\vec{f}. It suffices to show that a triangle is charged with at most k2k^2 curves for each of the six listed pairs. By symmetry, it suffices to analyze only two cases, namely when (e,f)=(xy,xz)(e,f)=(xy,xz) and (e,f)=(yx,zx)(e,f)=(yx,zx) (see Figure 8).

The two cases in the proof of Lemma 2.6(b)

Figure 8. The two cases in the proof of Lemma 2.6(b). The set SS consists of highlighted curves, which connect xyxy to xzxz. The orders of xyxy and xzxz agree on SS.

First, let (e,f)=(xy,xz)(e,f)=(xy,xz), and assume that the triangle xyzxyz is to the left of xy→\overrightarrow{xy}, as otherwise we can switch yy and zz. Let SS be the set of triples (α,p,q)(\alpha,p,q) for which the curve α\alpha joins the points p∈xy∩αp\in xy\cap\alpha and q∈xz∩αq\in xz\cap\alpha without exiting the triangle xyzxyz. Then SS can be naturally identified with subsets of both CxyC_{xy} and CxzC_{xz}.

Our goal is now to count the number of triples (α,p,q)∈S(\alpha,p,q)\in S for which the successors of (α,p)(\alpha,p) at xyxy and (α,q)(\alpha,q) at xzxz come from different curves. From their definition, we see that the orders ≺Lxy,≺Rxy\prec_{L}^{xy},\prec_{R}^{xy} agree with ≺Lxz,≺Rxz\prec_{L}^{xz},\prec_{R}^{xz} on SS. Under this identifications, the successors in the decomposition of SS on the two edges xy,xzxy,xz agree.

Note that SS is the set of first ∣S∣|S| elements in CxyC_{xy} under ≺Lxy\prec_{L}^{xy} (this is illustrated in Figure 8, since the edges of SS have the left endpoint “below” the other curves intersecting xyxy). Hence, (3) in Lemma 2.5 implies that D(S,Cxy)≤k−1\mathcal{D}(S,C_{xy})\le k-1. Similarly, SS is the set of smallest ∣S∣|S| elements in CxzC_{xz} under ≺Rxz\prec_{R}^{xz}, and so (1) in Lemma 2.5 implies that D(S,Cxz)≤(k2)\mathcal{D}(S,C_{xz})\le\binom{k}{2}. Thus, the number of elements of SS with different successors in CxyC_{xy} and CxzC_{xz} is at most D(S,Cxy)+D(S,Cxz)≤(k2)+k−1≤k2\mathcal{D}(S,C_{xy})+\mathcal{D}(S,C_{xz})\le\binom{k}{2}+k-1\le k^2.

The argument proceeds very similarly when (e,f)=(yx,zx)(e,f)=(yx,zx). Assuming now that xyzxyz is to the left of yx→\overrightarrow{yx}, we define SS as before, and observe that it is a subset of both CyxC_{yx} and CzxC_{zx}. In this case, SS is the set of last ∣S∣|S| elements in CyxC_{yx} under ≺Lyx\prec_{L}^{yx}, and therefore (4) in Lemma 2.5 implies that D(S,Cyx)≤(k2)\mathcal{D}(S,C_{yx})\le\binom{k}{2}. On the other hand, SS is also the set of largest ∣S∣|S| elements in CzxC_{zx} under ≺Rzx\prec_{R}^{zx}, and therefore (2) in Lemma 2.5 shows that D(S,Czx)=0\mathcal{D}(S,C_{zx})=0. This is illustrated in Figure 8(b). Hence, the number of elements of SS with different successors in CyxC_{yx} and CzxC_{zx} is at most D(S,Cyx)+D(S,Czx)≤(k2)+0≤k2\mathcal{D}(S,C_{yx})+\mathcal{D}(S,C_{zx})\le\binom{k}{2}+0\le k^2.

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 ℓS(x)\ell_S(x) and ℓS′(x)\ell_{S'}(x) can differ in each of the cases.

Proof of Lemma 2.5. We consider the four cases individually. Recall that for x∈Sx\in S, ℓS(x)\ell_S(x) denotes the length of the longest decreasing sequence in SS ending with xx. Throughout the proof, we think of S,S′S,S' as sequences, where xx comes before yy if x≺Lyx\prec_L y.

(1) We begin with two preparatory claims. First, we claim that if xx comes before yy in SS and both belong to the same increasing sequence in the decomposition of SS, i.e. ℓS(x)=ℓS(y)\ell_S(x)=\ell_S(y), then ℓS′(x)≤ℓS′(y)\ell_{S'}(x)\le\ell_{S'}(y).

Assume for contradiction that there exist x,y∈Sx,y\in S violating this statement. Among all such pairs (x,y)(x,y), choose one that minimizes ℓ=ℓS(x)\ell=\ell_S(x). Let LL be a decreasing subsequence of S′S' of length ℓS′(x)\ell_{S'}(x) ending at xx. Note that if all elements of L∖{x}L \setminus\{x\} are in S′∖SS' \setminus S, then replacing xx by yy in the sequence LL yields a decreasing subsequence of length ℓS′(x)\ell_{S'}(x) ending at yy, giving ℓS′(x)≤ℓS′(y)\ell_{S'}(x) \le\ell_{S'}(y). Let x′x' be the element of LL preceding xx, then x′∈Sx' \in S. If y≺Rx′y \prec_R x', then replacing xx with yy in LL would again yield a decreasing subsequence of length ℓS′(x)\ell_{S'}(x), so we must have x′≺Ryx' \prec_R y. Moreover, ℓS(x′)<ℓS(x)=ℓ\ell_S(x') < \ell_S(x) = \ell. Let y′∈Sy' \in S be such that ℓS(y′)=ℓS(x′)\ell_S(y') = \ell_S(x') and y′y' lies on a decreasing subsequence of length ℓS(y)\ell_S(y) ending at yy in SS. As x′≺Ry≺Ry′x' \prec_R y \prec_R y', we have x′≺Ry′x' \prec_R y'. By the minimality of ℓ\ell, we must have ℓS′(y′)≥ℓS′(x′)=ℓS′(x)−1\ell_{S'}(y') \ge\ell_{S'}(x') = \ell_{S'}(x) - 1, and hence ℓS′(y)≥ℓS′(y′)+1≥ℓS′(x)\ell_{S'}(y) \ge\ell_{S'}(y') + 1 \ge\ell_{S'}(x), a contradiction.

Next, we state and prove our second claim. It states that if xx comes before yy in SS and ℓS′(x)=ℓS′(y)\ell_{S'}(x) = \ell_{S'}(y), then ℓS(y)≤ℓS(x)\ell_S(y) \le\ell_S(x).

Assume for contradiction that for some xx preceding yy in SS, we have ℓS′(x)=ℓS′(y)\ell_{S'}(x) = \ell_{S'}(y) and ℓS(x)<ℓS(y)\ell_S(x) < \ell_S(y). Consider a decreasing subsequence of SS of length ℓS(y)\ell_S(y) ending at yy, and let y′y' be an element of this sequence such that ℓS(y′)=ℓS(x)\ell_S(y') = \ell_S(x). We have x≺Ry≺Ry′x \prec_R y \prec_R y', and thus y′y' lies between xx and yy in the sequence. Then, by the previous claim, we get ℓS′(y′)≥ℓS′(x)\ell_{S'}(y') \ge\ell_{S'}(x), and therefore ℓS′(y)≥ℓS′(y′)+1>ℓS′(x)\ell_{S'}(y) \ge\ell_{S'}(y') + 1 > \ell_{S'}(x), a contradiction.

Consider LS(ℓ)L_S(\ell), i.e. the increasing sequences in the decomposition of SS composed of elements x∈Sx \in S such that ℓS(x)=ℓ\ell_S(x) = \ell. Let x1,…,xpx_1, \ldots, x_p be the elements of LS(ℓ)L_S(\ell) which have different successors in SS and S′S'. We claim that

ℓ≤ℓS′(x1)<ℓS′(x2)<⋯<ℓS′(xp)≤k−1.(1)\ell\le\ell_{S'}(x_1) < \ell_{S'}(x_2) < \cdots< \ell_{S'}(x_p) \le k - 1. \tag*{(1)}

The first of these inequalities follows since ℓS′(x1)≥ℓS(x1)=ℓ\ell_{S'}(x_1) \ge\ell_S(x_1) = \ell, while the last one ℓS′(xp)≤k−1\ell_{S'}(x_p) \le k - 1 follows since S′S' contains no decreasing subsequence of length kk.

Hence, it remains to prove that for 1≤i<p1 \le i < p, we have ℓS′(xi)<ℓS′(xi+1)\ell_{S'}(x_i) < \ell_{S'}(x_{i+1}). Let yy be the successor of xix_i in SS. By the first claim applied to the pairs (xi,y)(x_i, y) and (y,xi+1)(y, x_{i+1}) (noting that both pairs satisfy the assumptions of the claim by definition), we have ℓS′(xi+1)≥ℓS′(y)≥ℓS′(xi)\ell_{S'}(x_{i+1}) \ge\ell_{S'}(y) \ge\ell_{S'}(x_i), so it suffices to show that ℓS′(y)>ℓS′(xi)\ell_{S'}(y) > \ell_{S'}(x_i).

Suppose we had ℓS′(y)=ℓS′(xi)\ell_{S'}(y) = \ell_{S'}(x_i). If y′≠yy' \ne y is the successor of xix_i in S′S', then y′y' is between xix_i and yy in the sequence S′S' and has ℓS′(xi)=ℓS′(y′)\ell_{S'}(x_i) = \ell_{S'}(y'). So, yy and y′y' are in the same increasing sequence of S′S', and we would have y′≺Ryy' \prec_R y. As SS is the set of ∣S∣|S| smallest elements under ≺R\prec_R, this implies y′∈Sy' \in S. Applying the second claim to the pairs (xi,y′)(x_i, y') and (y′,y)(y', y) then shows that ℓS(y′)≤ℓS(xi)\ell_S(y') \le\ell_S(x_i) and ℓS(y)≤ℓS(y′)\ell_S(y) \le\ell_S(y'). As ℓS(xi)=ℓS(y)\ell_S(x_i) = \ell_S(y), this quantity equals ℓS(y′)\ell_S(y'), which means that y′y' is in the same increasing sequence of SS as xix_i and yy. But then yy cannot be the successor of xix_i in SS, contradiction.

We proved that in LS(ℓ)L_S(\ell), there are p≤k−ℓp \le k - \ell elements whose successor is changed. Thus, the statement of (1) is then immediately obtained by summing over ℓ=1,…,k−1\ell= 1, \ldots, k - 1, i.e. D(S,S′)≤(k−1)+⋯+1=(k2)\mathcal{D}(S,S') \le(k - 1) + \cdots+ 1 = \binom{k}{2}.

(2) Clearly, we have ℓS(x)=ℓS′(x)\ell_S(x) = \ell_{S'}(x) for all x∈Sx \in S as no decreasing subsequence ending at xx can contain an element from S′∖SS' \setminus S. Moreover, for every x∈Sx \in S and y∈S′∖Sy \in S' \setminus S such that xx precedes yy, we have ℓS′(y)≥ℓS(x)+1\ell_{S'}(y) \ge\ell_S(x) + 1, as we can append yy to every decreasing subsequence ending at xx. This implies that all x∈Sx \in S have the same successor in both SS and S′S'.

(3) As in the previous case, we have ℓS(x)=ℓS′(x)\ell_S(x) = \ell_{S'}(x) for all x∈Sx \in S as these value do not depend on elements y∈S′y \in S' for which xx precedes yy. It immediately follows that every x∈Sx \in S that has a successor in SS has the same successor in S′S'. Only the elements of SS with no successor in SS can gain a successor in S′S', showing that D(S,S′)≤k−1\mathcal{D}(S,S') \le k - 1.

(4) We show that (1) implies (4) by a symmetry argument.

Let ≺L\prec_L be the reverse of ≺R\prec_R, and let ≺R\prec_R be the reverse of ≺L\prec_L on S′S'. To minimize confusion, we denote by T,T′T,T' the sets S,S′S,S' when they are ordered using the orders ≺L,≺R\prec_L,\prec_R. Observe that reversing an increasing sequence with respect to ≺L,≺R\prec_L,\prec_R gives an increasing sequence in ≺L,≺R\prec_L,\prec_R. On the other hand, a decreasing sequence with respect to orders ≺L,≺R\prec_L,\prec_R remains decreasing with respect to orders ≺L,≺R\prec_L,\prec_R. In particular, for every element xx, the length of the longest decreasing sequence ending at xx is unchanged, i.e. ℓS(x)=ℓT(x)\ell_S(x)=\ell_T(x) and ℓS′(x)=ℓT′(x)\ell_{S'}(x)=\ell_{T'}(x). Hence, the successor of xx in TT (or T′T') is the predecessor of xx in SS (or S′S'). The predecessor of xx is the element immediately before it in its increasing sequence in the Erdős-Szekeres decomposition.

The main advantage of this transformation is that TT is now the set of smallest ∣T∣|T| elements in T′T' under ≺R\prec_R, which corresponds to the situation of (1). To bound D(S,S′)D(S,S'), we bound the number of elements x∈Tx\in T with different predecessors in TT and T′T'. If the starting elements of the increasing sequences are the same in TT and T′T', then the number of x∈Tx\in T whose predecessor changes is at most D(T,T′)D(T,T') (which is at most (k2)\binom{k}{2} by (1)). The reason is simple: if x′x' was the predecessor of xx in TT, but is not in T′T', then the successor of x′x' must have changed from TT to T′T'.

To ensure that the increasing sequences in both TT and T′T' start with the same elements, add to the start of both sequences a set AA consisting of k−1k-1 dummy elements with ak−1≺R⋯≺Ra1a_{k-1}\prec_R\cdots\prec_R a_1 and a1≺La2≺L⋯≺Lak−1a_1\prec_L a_2\prec_L\cdots\prec_L a_{k-1}, such that ai≺Rxa_i\prec_R x and ai≺Lxa_i\prec_L x for all ai∈A,x∈T′a_i\in A,x\in T'. A dummy and a real element cannot be in the same decreasing sequence, and so the increasing sequences in both TT and T′T' start with a1,…,ak−1a_1,\ldots,a_{k-1}. Therefore, D(S,S′)≤D(A∪T,A∪T′)≤(k2)D(S,S')\leq D(A\cup T,A\cup T')\leq\binom{k}{2}, where the last inequality follows from (1), since A∪TA\cup T is the set of smallest ∣A∣+∣T∣|A|+|T| elements in A∪T′A\cup T' under ≺R\prec_R. □\square

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 ≺L,≺R\prec_L,\prec_R 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. [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. [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. [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. [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. [5]B. Beeker, and N. Lazarovich. Cubical accessibility and bounds on curves on surfaces. Journal of Topology 10 (2017): 1050–1065.DOI
  6. [6]J. F. Brandenburg. A simple quasi-planar drawing of K₁₀. In Graph Drawing, vol. 9801 (2016): 603–604.
  7. [7]P. Brass, W. Moser, and J. Pach. Research Problems in Discrete Geometry. Berlin, Germany, Springer-Verlag, 2005.DOI
  8. [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. [9]P. Erdős, and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica 2 (1935): 463–470.
  10. [10]I. Fáry. On straight-line representation of planar graphs Acta Sci. Math. (Szeged), 11 (1948): 229–233.
  11. [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. [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. [13]J. Pach, N. Rubin, and G. Tardos. Planar point sets determine many pairwise crossing segments. Advances in Mathematics 386 (2021): 107779.
  14. [14]J. Pach, F. Shahrokhi, and M. Szegedy. Applications of the crossing number. J. Graph Theory 22 (1996): 239–243.
  15. [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. [16]A. Sadhu. Every k-Quasi-Planar Graph Has Linearly Many Edges. preprint, arXiv:2611.01509 (2026)
  17. [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. [18]G. Tóth. Note on Geometric Graphs. Journal of Combinatorial Theory, Series A 89 (2000): 126–132.DOI
  19. [19]P. Valtr. Graph drawing with no k pairwise crossing edges. International Symposium on Graph Drawing. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997.DOI
  20. [20]P. Valtr. On geometric graphs with no k pairwise parallel edges. Discrete Comput. Geom. 19 (1998): 461–469.DOI

Paper details

vlnc:W_jtmadbfj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents