On the Maximum Number of Tangencies Among 1-Intersecting Curves

Ackerman, Eyal; Keszegh, Balázs

doi:10.4230/LIPIcs.SoCG.2026.2

On the Maximum Number of Tangencies Among $1$ -Intersecting Curves

Eyal Ackerman

Department of Mathematics, Physics and Computer Science, University of Haifa at Oranim, Israel Balázs Keszegh

HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary
ELTE Eötvös Loránd University, Budapest, Hungary

Abstract

According to a conjecture of Pach, there are $O(n)$ tangent pairs among any family of $n$ Jordan arcs in which every pair of arcs has precisely one common point and no three arcs share a common point. This conjecture was proved for two special cases, however, for the general case the currently best upper bound is only $O(n^{7/4})$ . This is also the best known bound on the number of tangencies in the relaxed case where every pair of arcs has at most one common point. We improve the bounds for the latter and former cases to $O(n^{5/3})$ and $O(n^{3/2})$ , respectively. We also consider a few other variants of these questions, for example, we show that if the arcs are $x$ -monotone, each pair intersects at most once and their left endpoints lie on a common vertical line, then the maximum number of tangencies is $\Theta(n^{4/3})$ . Without this last condition the number of tangencies is $O(n^{4/3}(\log n)^{1/3})$ , improving a previous bound of Pach and Sharir. Along the way we prove a graph-theoretic theorem which extends a result of Erdős and Simonovits and may be of independent interest.

Keywords and phrases:

tangency graph, forbidden subgraph, extremal graph

Funding:

Balázs Keszegh: Supported by the ERC Advanced Grant “ERMiD”, no. 101054936 and by the EXCELLENCE-24 project no. 151504 Combinatorics and Geometry of the NRDI Fund.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Extremal graph theory ; Mathematics of computing

\rightarrow

Graphs and surfaces

Related Version:

Full version: https://arxiv.org/abs/2603.11885 [2]

Acknowledgements:

We are grateful to Rom Pinchasi for many helpful discussions on the problems studied in this paper. In particular he has suggested most of the ingredients of the proofs of Theorems 7 and 5 and later found out that similar results were already proved by Pach and Sharir [23]. We thank Balázs Patkós for his comments about Theorem 9. For the proof of Theorem 10 we used some back and forth interaction with Google’s Large Language Model “Gemini” (https://gemini.google.com/).

DOI:

10.4230/LIPIcs.SoCG.2026.2

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Arrangements of curves play an important role in Computational and Combinatorial Geometry with applications in domains such as robotics, computer graphics, computer vision, and combinatorial optimization [24]. Many interesting problems in these areas can be phrased as determining the maximum number of tangencies among curves under various restrictions. For example, occasionally, analyzing the complexity of an arrangement of curves boils down to estimating the number of faces of size two [5]. Such faces can often be perturbed into tangency points. Another example is Erdős’s famous Unit Distance Problem which asks for the maximum number of pairs of points that are at unit distance from each other among $n$ distinct points in the plane. This is equivalent to asking for the maximum number of tangencies among $n$ unit circles in the plane.

Throughout this paper we consider planar curves, that is, Jordan arcs, and assume that every two curves intersect in a finite number of points. A family of curves is $k$ -intersecting if every two curves in it intersect in at most $k$ points. Two curves are said to be tangent or touching if they have precisely one common point and this point is not a crossing point.¹¹1Here we follow the definition in, e.g., [22]. In other papers, e.g., [9], two curves may cross and also touch each other (at different points). However, for $1$ -intersecting curves the two definitions coincide. We will mainly consider the maximum number of tangencies among families of $1$ -intersecting curves. Such families are sometimes called pseudo-segments.²²2However, the term “pseudo-segments” is somewhat ill-suited in the context of tangencies, since straight-line segments can only be tangent at an endpoint. A family of curves is precisely $1$ -intersecting if every pair of curves has precisely one common point (either a crossing or a tangency point). We will always assume that no three curves share a common point, for otherwise, it is possible to have one point at which every pair of curves is tangent. Therefore, the number of tangent pairs is equal to the number of tangency points.

János Pach proposed the following nice conjecture.

Conjecture 1 (Pach [20]).

Every family of $n$ precisely $1$ -intersecting planar curves in which no three curves share a common point admits $O(n)$ tangencies.

Györgyi et al. [14] proved this conjecture for the very special case where the endpoints of the curves lie within a constant number of cells of their arrangement. Conjecture 1 was also settled by the authors for $x$ -monotone curves [4]. Recall that a curve is $x$ -monotone (resp., bi-infinite $x$ -monotone) if it is the graph of some continuous function over some closed interval (resp., over $\mathbb{R}$ ). For arbitrary families of (precisely) $1$ -intersecting curves a non-trivial $O(n^{7/4})$ bound on the number of tangencies follows from a result of Keszegh and Pálvölgyi [17]:

Theorem 2 ( [17]).

Every family of $n$ $k$ -intersecting planar curves admits $O_{k}\left(n^{2-\frac{1}{k+3}}\right)$ tangencies.

We improve this bound for (precisely) $1$ -intersecting families as follows.

Theorem 3.

Every family of $n$ $1$ -intersecting planar curves admits $O(n^{5/3})$ tangencies.

Theorem 4.

Every family of $n$ precisely $1$ -intersecting planar curves admits $O(n^{3/2})$ tangencies.

Note that the maximum number of tangencies among $n$ ( $x$ -monotone) $1$ -intersecting curves is $\Omega(n^{4/3})$ . Indeed, it is not hard to construct a family admitting that many tangencies based on the famous construction of Erdős (see [21]) of $n$ lines, $n$ points and $\Theta(n^{4/3})$ point-line incidences (see the proof of Theorem 6).

For $x$ -monotone $1$ -intersecting curves we have the following bound.

Theorem 5.

Every family of $n$ $1$ -intersecting $x$ -monotone planar curves admits $O\left(n^{4/3}(\log n)^{1/3}\right)$ tangencies.

This bound almost matches the above-mentioned $\Omega(n^{4/3})$ lower bound and improves by an $O\left((\log n)^{1/3}\right)$ factor a previous bound that follows from a result of Pach and Sharir [23]. For so-called grounded $x$ -monotone $1$ -intersecting curves we have an asymptotically tight bound.

Theorem 6.

The maximum number of tangencies among $n$ $x$ -monotone $1$ -intersecting planar curves whose left endpoints lie on a common vertical line is $\Theta(n^{4/3})$ .

The proofs of Theorems 5 and 6 rely on the following bounds for bi-infinite curves.

Theorem 7.

The maximum number of tangencies among $n$ bi-infinite $x$ -monotone $1$ -intersecting curves is $\Theta(n\log n)$ . In case of precisely $1$ -intersecting curves the maximum number of tangencies is $n-1$ .

The bound for bi-infinite $x$ -monotone $1$ -intersecting curves was already proved by Pach and Sharir [23] using different and less elementary arguments. The following table summarizes all the above-mentioned results.

Table 1: Bounds on the maximum number of tangencies among

n

1

-intersecting curves.

	$x$ -monotone	arbitrary
bi-infinite $1$ -intersecting	$\Theta(n\log n)$ [23] (Thm 7)	–
bi-inf. precisely $1$ -inters.	$n-1$ (Thm 7)	–
grounded $1$ -intersecting	$\Theta(n^{4/3})$ (Thm 6)	$\Omega(n^{4/3})$ , $O(n^{3/2})$ (Cor 18)
$1$ -intersecting	$\Omega(n^{4/3})$ [23], $O(n^{4/3}(\log n)^{1/3})$ (Thm 5)	$\Omega(n^{4/3})$ , $O(n^{5/3})$ (Thm 3)
precisely $1$ -intersecting	$\Theta(n)$ [4]	$\Omega(n)$ , $O(n^{3/2})$ (Thm 4)

1.1 A graph-theoretic theorem

For a graph $H$ let $\mbox{ex}(n,H)$ denote the maximum number of edges in an $n$ -vertex $H$ -free graph, that is, a graph which does not contain $H$ as a subgraph. For a bipartite graph $H=\left(A\cup B,E\right)$ we denote by $H^{+}$ the graph we get by adding to $H$ two new adjacent vertices $a^{\prime}$ and $b^{\prime}$ and connecting $a^{\prime}$ to every vertex in $B$ and $b^{\prime}$ to every vertex in $A$ . That is, $H^{+}=\left((A\cup\{a^{\prime}\})\cup(B\cup\{b^{\prime}\}),E\cup\{(a^{\prime},% b^{\prime})\}\cup\{(a^{\prime},b)\mid b\in B\}\cup\{(a,b^{\prime})\mid a\in A% \}\right)$ . Erdős and Simonovits [10] proved the following result³³3We present a simplified version of their result from which the original version can be easily deduced. when studying $\mbox{ex}(n,Q_{3})$ , where $Q_{3}$ is the graph with $8$ vertices and $12$ edges that corresponds to a three-dimensional cube.

Theorem 8 ([10, Theorem 2]).

Let $H$ be a bipartite graph with at least one edge such that $\mbox{ex}(n,H)=O(n^{2-\alpha})$ for some constant $0\leq\alpha\leq 1$ . Then $\mbox{ex}(n,H^{+})=O\left(n^{2-\frac{\alpha}{\alpha+1}}\right)$ .

Observe that if $G=(A\cup B,E)$ is a bipartite $H^{+}$ -free graph, then for every adjacent vertices $a\in A$ and $b\in B$ it holds that $G[(N_{G}(a)\setminus\{b\})\cup(N_{G}(b)\setminus\{a\})]$ – the subgraph of $G$ induced by their open bineighborhood – is $H$ -free. Roughly speaking, if for every adjacent vertices in $G$ the subgraph induced by their open bineighborhoods is not too dense because it is $H$ -free, then it follows that $G$ is also not too dense. We extend and refine Theorem 8 by showing that it holds whenever we have sparse subgraphs induced by open sub-bineighborhoods of pairs of (adjacent) vertices, be it for $H$ -freeness or some other reason. To state the result we need the following definition: for a graph $G$ and a nonnegative and nondecreasing function $f:\mathbb{R}\rightarrow\mathbb{R}$ we say that two vertices $u$ and $v$ have $f$ -sparse sub-bineighborhoods if for every two disjoint subsets $U\subseteq N_{G}(u)\setminus\{v\}$ and $V\subseteq N_{G}(v)\setminus\{u\}$ it holds that $|E(G(U,V))|\leq f(|U\cup V|)$ , where $G(U,V)$ is the bipartite subgraph $(U\cup V,\{(u,v)\in E(G)\mid u\in U\textrm{ and }v\in V\})$ . For the proof of Theorem 3 we use the following theorem which extends Theorem 8 and may be of independent interest.

Theorem 9.

Let $G$ be a graph and let $f(n)=O(n^{2-\alpha})$ for some constant $0\leq\alpha<2$ . If every pair of vertices in $G$ has $f$ -sparse sub-bineighborhoods, then $|E(G)|=O\left(|V(G)|^{2-\frac{\alpha}{\alpha+1}}\right)$ . Moreover, if $\alpha\leq 1$ , then it is enough that every pair of adjacent vertices has $f$ -sparse sub-bineighborhoods for this bound to hold.

Clearly, Theorem 9 implies Theorem 8. Note that from Theorem 8 one can conclude by induction on $t$ the classical Kővári-Sós-Turán Theorem [18] stating that an $n$ -vertex $K_{t,t}$ -free graph has $O_{t}\left(n^{2-\frac{1}{t}}\right)$ edges. It is a major open question in extremal combinatorics whether this bound is tight with positive answers only known for $t=2$ and $t=3$ . Thus, the upper bound in Theorem 8 is tight for $\alpha=1$ and $\alpha=\frac{1}{2}$ , and, assuming that the bound of the Kővári-Sós-Turán Theorem is tight, for every $\alpha=\frac{1}{t}$ where $t$ is a positive integer. Remarkably, for Theorem 9 we do have a matching lower bound for every $0\leq\alpha\leq 1$ .

Theorem 10.

For every $0\leq\alpha\leq 1$ there is a bipartite graph $G=(V,E)$ with $|E|=\Omega\left(|V|^{2-\frac{\alpha}{\alpha+1}}\right)$ edges such that every pair of vertices in $G$ has $f$ -sparse sub-bineighborhoods where $f(n)=O(n^{2-\alpha})$ .

1.2 Related work

Agarwal, Nevo, Pach, Pinchasi, Sharir and Smorodinsky [5] proved that any family of $n$ pairwise intersecting $x$ -monotone bi-infinite $2$ -intersecting curves admits at most $2n-4$ tangencies. Families of $2$ -intersecting closed curves are called pseudo-circles. Erdős and Grünbaum [11] (see also [8, §7.1, Problem 14]) asked for the maximum number of tangencies among $n$ pseudo-circles. An $\Omega(n^{4/3})$ lower bound for this problem follows from the many point-line incidences construction. The best upper bound is $O(n^{3/2})$ by a recent result of Janzer, Janzer, Methuku and Tardos [16]. As for pairwise intersecting pseudo-circles, a recent work with Damásdi, Pinchasi and Raffay [1] settled an old conjecture of Grünbaum [13] by showing that the maximum number of tangencies is $2n-2$ in this case. A worse linear upper bound was proved in [5].

Ellenberg, Solymosi and Zahl [9] proved that any family of $n$ plane algebraic curves of degree at most $d$ admits $O_{d}(n^{3/2})$ tangencies.⁴⁴4As mentioned before, their notion of tangency is a bit different and they actually bound the number of tangency points. If two curves may intersect an arbitrary number of times, then it is possible to have $\Omega(n^{2})$ tangencies among $n$ curves. Solving a conjecture of Richter and Thomassen it was shown by Pach, Rubin and Tardos [22] that if every pair of $n$ closed curves intersects, then there are many more crossing points than tangency points. Specifically, they showed that if $X$ denotes the crossing points and $T$ denotes the tangency points, then $|X|=\Omega(|T|(\log\log n)^{1/8})$ and conjectured that $|X|=\Omega(|T|\log n)$ .

Another line of research studies the number of tangencies between two families each consisting of disjoint curves. This problem was introduced by Pach, Suk and Treml [25] who attributed it to Ben-Dan and Pinchasi [6]. An upper bound of $O(n^{3/2})$ follows from an observation of Ben-Dan and Pinchasi and from the result of Janzer et al. [16], whereas a lower bound of $\Omega{(n^{4/3})}$ was shown by Keszegh and Pálvölgyi [17] using $2$ -intersecting curves. For two families of $1$ -intersecting curves a linear upper bound was proved by Pálvölgyi et nos [3]. For further related results on tangencies among curves and their applications see [5] and [22] and the references therein.

Organization

After introducing some notations and collecting a few useful lemmas in Section 2, we prove the results for arbitrary $1$ -intersecting curves in Section 3. Our results for $x$ -monotone curves are presented and partially proved in Section 4. Finally, in Section 5 we prove Theorem 9 and discuss its further applications and connections to related graph theoretic results. Proofs that were omitted due to space limitation can be found in the full version of this paper [2].

2 Notations and Tools

Recall that we assume that every two curves intersect at finitely many points and that no three curves intersect at a single point. It follows from the former assumption that we may also assume that the curves are drawn as polygonal chains. Indeed, given a set of curves ${\cal C}$ , consider the plane graph $G$ whose vertex set consists of the endpoints and intersection points of the curves in ${\cal C}$ and whose edge set consists of subcurves between consecutive vertices along the curves. By Fáry’s Theorem [12] this planar graph can be embedded using straight-line edges and the same rotation system. Replacing every curve $c\in{\cal C}$ with the polygonal chain that consists of the edges in this embedding that correspond to edges of $G$ that belong to $c$ , we obtain a family of curves ${\cal C}^{\prime}$ such that for every intersection (resp., tangency) point of two curves in ${\cal C}$ there is a unique intersection (resp., tangency) point between their corresponding curves in ${\cal C}^{\prime}$ , and vice versa.

For a set of curves ${\cal C}$ we denote by $G_{\cal C}$ the tangency graph of ${\cal C}$ , that is, the graph whose vertex set is ${\cal C}$ and whose edge set consists of the tangent pairs of curves. By abuse of notation we sometimes interchange curves in ${\cal C}$ and their corresponding vertices in $G_{\cal C}$ .

Let $c$ be a curve and let $p$ and $q$ be two points on $c$ . We denote by $c[p,q]$ the subcurve of $c$ between these two points. For another curve $c^{\prime}$ that intersects $c$ at a single point, we may also write, e.g., $c[c^{\prime},q]$ instead of $c[c\cap c^{\prime},q]$ . If $c$ is oriented, then we denote by $c^{-}$ (resp., $c^{+}$ ) its starting (resp., terminating) point following its orientation. We also write $c[-,p]$ and $c[p,+]$ instead of $c[c^{-},p]$ and $c[p,c^{+}]$ , respectively. If $c$ is an $x$ -monotone curve and $p$ is a point (not necessarily on $c$ ), then with some abuse of notation by writing, e.g., $c[p,+]$ , we mean $c[\ell_{p}\cap c,+\infty)$ , where $\ell_{p}$ is the vertical line through $p$ . As usual, a round bracket indicates that an endpoint does not belong to the subcurve.

A family of $x$ -monotone curves induces a generalized trapezoidal partition of the plane in the following way. From every point $p$ which is an endpoint of a curve or an intersection point of two curves we draw a maximal vertical segment (possibly a ray or a line) that contains $p$ and does not cross any other curve but the ones containing $p$ . This yields a partition of the plane into generalized trapezoids.

Theorem 11 (Cutting Lemma for $x$ -monotone curves [15, Proposition 2.11]).

For every family ${\cal C}$ of $n$ $x$ -monotone $1$ -intersecting curves and any $r>1$ there is a subset of curves in ${\cal C}$ which induces a generalized trapezoidal partition of the plane into $O(r^{2})$ generalized trapezoids each intersected by at most $n/r$ curves from ${\cal C}$ .

We will also make use of the (asymmetric) Kővári-Sós-Turán Theorem and the recent tight bound of Janzer et al. [16] on the size of intersection-reverse sequences. The latter improves previous bounds by Marcus and Tardos [19] and by Pinchasi and Radoičić [26].

Theorem 12 (Kővári-Sós-Turán Theorem [18]).

For every $m,n,s,t\geq 1$ if $G=(A\cup B,E)$ is a bipartite graph such that $|A|=m$ , $|B|=n$ , and there are no $s$ vertices in $A$ and $t$ vertices in $B$ that form a complete bipartite subgraph $K_{s,t}$ , then $|E|\leq(s-1)^{1/t}nm^{1-1/t}+(t-1)m$ . In particular, $|E|=O_{s}(n^{2-1/t})$ when $m=n$ and $s\geq t$ .

Theorem 13 ([16]).

Let $A^{1},\ldots,A^{n}$ be linear orders on some subsets of a set of $n$ symbols such that no three symbols appear in the same order in any two distinct linear orders. Then $\sum_{i=1}^{n}|A^{i}|=O(n^{3/2})$ .

3 Arbitrary $1$ -intersecting curves

In this section we consider $1$ -intersecting curves that are not necessarily $x$ -monotone and prove Theorems 3 and 4. We begin with grounded curves. A family of curves ${\cal C}$ is grounded at a curve $c\notin{\cal C}$ if every curve in ${\cal C}$ has an endpoint on $c$ .

Theorem 14.

Let $A$ be a family of curves grounded at a curve $\ell_{A}$ and let $B$ be a family of curves grounded at a curve $\ell_{B}$ , such that all of these curves form a family of $1$ -intersecting curves, no curve in $A\cup\{\ell_{A}\}$ intersects $\ell_{B}$ and no curve in $B\cup\{\ell_{B}\}$ intersects $\ell_{A}$ . Then the number of tangent pairs $\{c_{A}\in A,c_{B}\in B\}$ is $O(|A\cup B|^{3/2})$ .

Proof.

We refer to the curves in $A$ as red curves and to the curves in $B$ as blue curves. If a pair of curves of the same color touch, then we may redraw them locally such that they are disjoint, since we only care about red-blue tangencies. Thus, every pair of curves of the same color are either crossing or disjoint. Orient each curve in $A$ away from $\ell_{A}$ and each curve in $B$ away from $\ell_{B}$ . Then, there are four types of red-blue tangencies since every curve has a “left” side and a “right” side with respect to its orientation.

Proposition 15.

Let $c,c_{1},c_{2}$ and $\ell$ be four distinct curves such that: (1) $\{c,c_{1},c_{2},\ell\}$ is $1$ -intersecting; (2) $c_{1}$ and $c_{2}$ are grounded at $\ell$ and are oriented away from $\ell$ ; (3) $c$ is oriented and touches $c_{1}$ and $c_{2}$ at tangency points of the same type; and (4) $c$ and $\ell$ are disjoint. Then $c_{1}[c,+]$ and $c_{2}[c,+]$ do not cross.

Proof.

Suppose that $c_{1}[c,+]$ and $c_{2}[c,+]$ cross and let $T$ denote the simple closed curve $c[c_{1},c_{2}]\cup c_{1}[c,c_{2}]\cup c_{2}[c,c_{1}]$ , see Figure 1. Then $c_{1}^{-}$ and $c_{2}^{-}$ lie on different sides $T$ .⁵⁵5Assuming some arbitrary orientation of $T$ , disregarding the orientations of the other curves. However, this is impossible since both of these points are on $\ell$ which cannot cross $T$ .

Figure 1: If

c_{1}

and

c_{2}

are grounded at

\ell

and have the same tangency type with

c

, then

c_{1}[c,+]

and

c_{2}[c,+]

cannot cross.

$\hfill\blacktriangleleft$

Returning to the proof of the theorem, we consider each of the four tangency types separately. For a certain type $t$ , we write for each curve $b\in B$ the ordered list of curves from $A$ that touch $b$ at a touching point of the given type. The list, denote it by $l_{t}(b)$ , is ordered according to the order of the corresponding touching points along $b$ .

Proposition 16.

There are no three curves $a_{1},a_{2},a_{3}\in A$ and two curves $b_{1},b_{2}\in B$ such that $a_{1},a_{2},a_{3}$ appear in this order both in $l_{t}(b_{1})$ and in $l_{t}(b_{2})$ .

Proof.

Suppose for contradiction that there are such curves. Observe first that it follows from Proposition 15 that $b_{1}[a_{1},+]$ and $b_{2}[a_{1},+]$ do not cross. In particular $b_{1}[a_{1},a_{3}]$ and $b_{2}[a_{1},a_{3}]$ do not cross. Next, we claim that at least one pair of the three subcurves $a_{i}[b_{1},b_{2}]$ , $i=1,2,3$ , is crossing. Suppose for contradiction that these curves are pairwise disjoint. Slightly “inflate” $b_{1}$ and $b_{2}$ and fix a point $p(c)$ on each subcurve $c\in\{a_{1}(b_{1},b_{2}),a_{2}(b_{1},b_{2}),a_{3}(b_{1},b_{2}),b_{1}(a_{1},a_{% 3}),\allowbreak b_{2}(a_{1},a_{3})\}$ . Note that these subcurves are disjoint. Next, draw a crossing-free copy of $K_{2,3}$ whose vertices are these five points and whose edges follow the corresponding subcurves, as suggested by Figure 2.

Figure 2: If the subcurves

a_{i}(b_{1},b_{2})

were disjoint, then we could draw a crossing-free copy of

K_{2,3}

.

Note that since $a_{1},a_{2},a_{3}$ touch in this order both of $b_{1}$ and $b_{2}$ , the counterclockwise cyclic order of $p(a_{1}),p(a_{2}),p(a_{3})$ is the same for $p(b_{1})$ and $p(b_{2})$ . However, this contradicts the following lemma of Pinchasi and Radoičić [26].

Lemma 17 ([26, Lemma 1]).

Let $G$ be a topological graph with no two edges belonging to a $4$ -cycle that crosses itself an odd number of times. For each vertex $v$ of $G$ let $C_{v}$ denote the counterclockwise cyclic order of the neighbors of $v$ . Then for each pair of vertices $u$ and $v$ , if there are more than two common neighbors of $u$ and $v$ , then the order of these neighbors in $C_{v}$ is reversed with respect to their order in $C_{u}$ .

For the rest of the proof we will only consider the guaranteed pair of crossing subcurves among $a_{i}[b_{1},b_{2}]$ , $i=1,2,3$ , therefore we may suppose without loss of generality that $a_{1}(b_{1},b_{2})$ and $a_{2}(b_{1},b_{2})$ are crossing. We may also assume that $a_{1}$ meets $b_{1}$ before meeting $b_{2}$ . Since $a_{1}[b_{1},+]$ cannot cross $a_{2}[b_{1},+]$ by Proposition 15, it follows that $a_{1}[b_{1},+]$ and $a_{2}[-,b_{1}]$ are crossing. Together with $b_{1}[a_{1},a_{2}]$ and $b_{2}[a_{1},a_{2}]$ they induce a partition of the plane into three connected regions. For each type of red-blue tangency, the points $a_{1}^{-}$ and $a_{2}^{-}$ lie on two different regions, see Figure 3 for an illustration.

Figure 3: Illustrations for the proof of Proposition 16:

a_{1}[b_{1},+]

and

a_{2}[-,b_{1}]

are crossing and together with

b_{1}[a_{1},a_{2}]

and

b_{2}[a_{1},a_{2}]

induce a partition of the plane.

a_{1}^{-}

and

a_{2}^{-}

lie on different regions of this partition for any red-blue tangency type.

However, this is impossible since both of these points lie on $\ell_{A}$ which does not cross any of the curves $a_{1},a_{2},b_{1},b_{2}$ . $\hfill\blacktriangleleft$

It follows from Proposition 16 and Theorem 13 that $\sum_{i}|l_{t}(b_{i})|=O(|A\cup B|)^{3/2}$ . Therefore, the number of red-blue tangencies is also $O(|A\cup B|)^{3/2}$ . $\hfill\blacktriangleleft$

Corollary 18.

Let ${\cal C}$ be a family of $n$ $1$ -intersecting curves grounded at a curve $\ell$ . Then the number of tangencies among ${\cal C}$ is $O(n^{3/2})$ .

Proof.

Denote by $t(n)$ the maximum number of tangencies among such a family of $n$ curves. We prove that $t(n)=O(n^{3/2})$ by induction on $n$ . Split $\ell$ into two disjoint subcurves such that $n/2$ curves from ${\cal C}$ are grounded at each subcurve. Using Theorem 14 and induction we get the recursive relation $t(n)\leq 2t(n/2)+O(n^{3/2})$ which implies that $t(n)=O(n^{3/2})$ . $\hfill\blacktriangleleft$

Corollary 19.

Let $A$ be a family of curves grounded at a curve $\ell_{A}$ and let $B$ be a family of curves grounded at a curve $\ell_{B}$ , such that $A\cup B\cup\{\ell_{A},\ell_{B}\}$ form a family of $1$ -intersecting curves. Then the number of tangent pairs $\{c_{A}\in A,c_{B}\in B\}$ is $O(|A\cup B|^{3/2})$ .

Proof.

If $\ell_{A}$ and $\ell_{B}$ cross at a point $p$ , then we split each of them into two curves at $p$ (such that $p$ belongs to neither of them). Denote these subcurves by $\ell_{A}^{1},\ell_{A}^{2},\ell_{B}^{1}$ and $\ell_{B}^{2}$ and note that each pair of them are disjoint. Every curve in $A$ (resp., $B$ ) that crosses $\ell_{B}$ (resp., $\ell_{A}$ ) we cut into two subcurves, such that one of them is grounded at $\ell_{A}^{1}$ or $\ell_{A}^{2}$ (or at $\ell_{A}$ if it was not cut) and the other is grounded at $\ell_{B}^{1}$ or $\ell_{B}^{2}$ (or at $\ell_{B}$ if it was not cut). It remains to bound the number of tangencies among curves grounded at $\ell_{x}^{i}$ , for each $x\in\{A,B\}$ and $i\in\{1,2\}$ , and the number of tangencies of pairs of curves $c$ and $c^{\prime}$ such that $c$ is grounded at $\ell_{x}^{i}$ and $c^{\prime}$ is grounded at $\ell_{y}^{j}$ for each $x,y\in\{A,B\}$ and $i,j\in\{1,2\}$ such that $x\neq y$ or $i\neq j$ . It follows from Corollary 18 and Theorem 14 that the total number of all of these tangencies is $O(|A\cup B|^{3/2})$ . $\hfill\blacktriangleleft$

We can now deduce the main results of this section. See 4

Proof.

Follows immediately from Corollary 18. $\hfill\blacktriangleleft$

Theorem 3. [Restated, see original statement.]

Every family of $n$ $1$ -intersecting planar curves admits $O(n^{5/3})$ tangencies.

Proof.

Let ${\cal C}$ be a family of $n$ $1$ -intersecting curves and let $G_{\cal C}$ be the tangency graph of ${\cal C}$ . It follows from Corollary 19 that $G_{\cal C}$ satisfies the $f$ -sparse sub-bineighborhoods property for $f(x)=O(x^{3/2})$ . Indeed, let $v_{0}$ and $v_{1}$ be two adjacent vertices in $G_{\cal C}$ and let $V_{i}\subseteq N_{G_{\cal C}}(v_{i})\setminus\{v_{1-i}\}$ , for $i=0,1$ , be two disjoint subsets of their neighborhoods in $G_{\cal C}$ . We wish to bound $t(V_{0},V_{1})$ – the number of tangent pairs $\{u_{0}\in V_{0},u_{1}\in V_{1}\}$ . For every $i=0,1$ and every curve $u\in V_{i}$ , we split $u$ into two subcurves $u_{i}^{\prime}$ and $u^{\prime\prime}_{i}$ such that each of them is grounded at $v_{i}$ . Denote the resulting set of curves by $V^{\prime}_{1},V^{\prime\prime}_{1},V^{\prime}_{2}$ and $V^{\prime\prime}_{2}$ , respectively. Thus, $t(V_{0},V_{1})=t(V^{\prime}_{0},V^{\prime}_{1})+t(V^{\prime}_{0},V^{\prime% \prime}_{1})+t(V^{\prime\prime}_{0},V^{\prime}_{1})+t(V^{\prime\prime}_{0},V^{% \prime\prime}_{1})$ . It follows from Corollary 19 that this sum is upper-bounded by $O(|V_{0}\cup V_{1})|^{3/2})$ . Therefore, by Theorem 9 we have that $|E(G_{\cal C})|\leq O(n^{5/3})$ . $\hfill\blacktriangleleft$

4 Tangencies among $𝒙$ -monotone curves

Theorem 7 is proved in the full version of this paper [2]. Here we give a short summary of the ideas of the proof. First, in the case of exactly $1$ -intersecting bi-infinite $x$ -monotone curves we prove that the tangency graph cannot contain a cycle, thus has at most $n-1$ edges. Then we prove a linear bound for a bipartite variant of counting tangencies between two families of bi-infinite $x$ -monotone curves that are separated in the infinity and apply this to get the $O(n\log n)$ bound for the general $1$ -interesting case.

Next we show the main ideas needed to prove Theorem 5 and 6, the details are again in the full version of this paper [2].

Pach and Sharir [23] studied the following problem: What is the maximum number of pairs of disjoint line-segments that are vertically visible among a set of $n$ segments in the plane? We say that two segments are vertically visible if there exists a vertical segment that intersects both of them and does not intersect any other segment in the set. The motivation for this problem came from analyzing the maximum size of the events queue in the original implementation of the Bentley-Ottmann line sweeping algorithm for enumerating all the intersections among a set of segments [7].

Pach and Sharir [23] proved that the maximum number of pairs of disjoint vertically visible line-segments within a set of $n$ segments is $O\left(n^{4/3}\left(\log n\right)^{2/3}\right)$ and $\Omega\left(n^{4/3}\right)$ . They also mentioned these bounds hold also for $x$ -monotone $1$ -intersecting curves.

It is easy to see that counting disjoint vertically visible pairs can be reduced to counting touching pairs of $x$ -monotone $1$ -intersecting curves and vice versa. Indeed, vertically visible curves can become tangent by replacing a very narrow part of one curve by a “spike” that touches the other curve. On the other hand, a pair of touching curves can be easily “detached” and become vertically visible. Therefore, the result of Pach and Sharir [23] implies that the maximum number of tangencies among $n$ $x$ -monotone $1$ -intersecting curves is $O\left(n^{4/3}\left(\log n\right)^{2/3}\right)$ and $\Omega\left(n^{4/3}\right)$ .

We outline the proof of the upper bound of Pach and Sharir [23] and point out the modifications which lead to the better bounds of Theorem 5 and 6. First, the cutting lemma (Theorem 11) is used to partition the plane into generalized trapezoids such that every trapezoid is cut by not too many curves. Then, the number of tangencies within every trapezoid $T_{i}$ is estimated and finally the sum over all the trapezoids is bounded. Regarding tangencies within $T_{i}$ , one considers two subsets of curves that cut $T_{i}$ : “short” curves that have at least one endpoint inside $T_{i}$ and “long” curves that have no endpoint inside $T_{i}$ . Therefore, the long curves behave like bi-infinite curves with respect to $T_{i}$ . Thus, the number of long-long tangencies can be bounded using the $O(n\log n)$ bound of Theorem 7. In order to obtain the tight upper bound of Theorem 6 we use for this case the linear bound for the case of counting tangencies between two families of bi-infinite $x$ -monotone curves that are separated in the infinity, see Lemma 2 in the full version of this paper [2]. The number of short-long tangencies is bounded using Kővári-Sós-Turán Theorem and a technical lemma (see the full version of this paper [2]). Finally, the number of short-short tangencies is bounded in [23] by further subdividing $T_{i}$ into vertical slabs. However, we observe that one can instead use induction and this simplifies the proof and leads to a better upper bound.

4.1 Bi-infinite $𝒌$ -intersecting $𝒙$ -monotone curves

In light of the second part of Theorem 7 and [5, Theorem 2.4] it is tempting to suggest that a similar statement holds for every fixed $k$ .

Conjecture 20.

Every set of $n$ pairwise intersecting bi-infinite $x$ -monotone $k$ -intersecting curves admits $O_{k}(n)$ tangencies.

We were unable to settle this conjecture. Still, we mention a simple and weak polynomial upper bound and two observations regarding the conjecture. For the upper bound we use the following observation.

Observation 21.

Let $r$ and $r^{\prime}$ be two bi-infinite $x$ -monotone curves touching from below an $x$ -monotone curve $b$ . Then $r$ and $r^{\prime}$ cross at a point whose $x$ -coordinate is between $b\cap r$ and $b\cap r^{\prime}$ .

By Theorem 2 we have $O_{k}\left(n^{2-\frac{1}{k+3}}\right)$ tangencies among any $n$ $k$ -intersecting curves. One can slightly improve upon this bound in case of bi-infinite $x$ -monotone curves.

Proposition 22.

Let ${\cal L}$ be a family of $k$ -intersecting bi-infinite $x$ -monotone curves. Then ${\cal L}$ admits $O_{k}\left(n^{2-\frac{1}{k+1}}\right)$ tangencies.

Proof.

Note that the curves in ${\cal L}$ are not necessarily pairwise intersecting. Consider the tangency graph $G_{\cal L}$ and flip a fair coin for every curve $c\in{\cal L}$ . If the outcome is “heads”, delete all the edges that correspond to tangencies in which $c$ touches another curve from below. Otherwise, if the outcome is “tails” do the same for tangencies in which $c$ touches a curve from above. Clearly, every edge in $G_{\cal L}$ survives with probability $1/4$ . Therefore, there is a bipartite subgraph $(B\cup R,E)$ with at least $|E(G_{\cal L})|/4$ edges in which every curve that corresponds to a vertex $r\in R$ touches from below the curves corresponding to its neighbors in $B$ . It suffices to bound the size of this subgraph.

We claim that this subgraph does not contain $K_{k+1,c_{k}}$ as a subgraph, for some large enough $c_{k}$ to be determined later. Indeed, suppose without loss of generality that there is a subset of $c_{k}$ curves $R^{\prime}=\{r_{1},r_{2},\ldots,r_{c_{k}}\}\subseteq R$ each of which touches from below each of the $k+1$ curves in a subset $B^{\prime}=\{b_{1},b_{2},\ldots,b_{k+1}\}\subseteq B$ . Let $\ell$ be the lower envelope of the curves in $B^{\prime}$ . Then $\ell$ consists of at most $\lambda_{k+2}(k+1)$ curve-segments, where $\lambda_{s}(n)$ denotes that maximum length of an $(n,s)$ -Davenport-Schinzel sequence [27].⁶⁶6A sequence of letters over an $n$ -element alphabet is an $(n,s)$ -Davenport-Schinzel sequence if it does not contain two consecutive identical letters and no alternating sub-sequence of two letters whose length is $s+2$ . In fact a trivial bound of $O(k^{3})$ on the size of the lower envelope also suffices for our purpose. Note that each curve $r^{\prime}\in R^{\prime}$ touches $k+1$ of these curve-segments (which belong to $k+1$ different curves in $B^{\prime}$ ). Therefore, there are at most $\binom{\lambda_{k+2}(k+1)}{k+1}$ possibilities for the $(k+1)$ -subset of curve-segments of $\ell$ that a curve in $R^{\prime}$ touches. Setting $c_{k}=1+\binom{\lambda_{k+2}(k+1)}{k+1}$ implies that there are two curves $r^{\prime},r^{\prime\prime}\in R^{\prime}$ that touch the same $k+1$ curve-segments of $\ell$ . Consider one of these curve-segments $s$ . Then it follows from Observation 21 that $r^{\prime}$ and $r^{\prime\prime}$ cross at a point whose $x$ -coordinate is between $s\cap r^{\prime}$ and $s\cap r^{\prime\prime}$ . Since the $k+1$ curve-segments that $r^{\prime}$ and $r^{\prime\prime}$ touch have distinct $x$ -projections, it follows that $r^{\prime}$ and $r^{\prime\prime}$ cross at least $k+1$ times, which is impossible. Thus, $(B\cup R,E)$ is a $K_{k+1,c_{k}}$ -free graph and it follows from Kővári-Sós-Turán Theorem that it has at most $O_{k}\left(n^{2-\frac{1}{k+1}}\right)$ edges. $\hfill\blacktriangleleft$

The next observation says that if Conjecture 20 is true, then the same statement holds without requiring the curves to be bi-infinite.

Proposition 23.

Suppose that Conjecture 20 holds for some $k>2$ . Then every set of $n$ pairwise intersecting $x$ -monotone $(k-2)$ -intersecting curves admits $O_{k}(n)$ tangencies.

Proof.

Let ${\cal L}$ be a set of curves as in the proposition. We assume without loss of generality that no two endpoints of two curves share the same $x$ -coordinate. There are four types of tangencies: the curve touching from above starts before/after the curve touching from below and ends before/after it. We consider each type separately and observe that the set of curves touching from above and the set of curves touching from below are disjoint sets. Call the curves in the first set red and the curves in the other set blue. Next, we extend each red curve into a bi-infinite curve by shooting a very steep ray leftwards (resp., rightwards) and upwards at its left (resp., right) endpoint. Similarly, we extend each blue curve into a bi-infinite curve by shooting a very steep ray leftwards (resp., rightwards) and downwards at its left (resp., right) endpoint. The rays going leftward and upwards and the rays going rightwards and downwards have opposite slopes. Similarly, the rays going leftward and downwards and the rays going rightwards and upwards have opposite slopes. Note that this introduces at most two new intersection points between two curves while for touching curves (of the considered type) no new intersection point is introduced. $\hfill\blacktriangleleft$

According to the following observation for an even $k$ we may assume that every non-tangent pair of curve intersects at exactly $k$ points.

Proposition 24.

Let ${\cal L}$ be a set of $n$ bi-infinite $x$ -monotone curves such that every pair of curves in ${\cal L}$ intersect at at least one and at most $k$ points for some even $k$ . Then there is a set ${\cal L}^{\prime}$ of $n$ bi-infinite $x$ -monotone curves such that every pair of curves in ${\cal L}^{\prime}$ is either touching at a single point or crossing at exactly $k$ points and the number of touching pairs in ${\cal L}$ and ${\cal L}^{\prime}$ is the same.

Proof.

We may assume without loss of generality that all the curves are parallel to the $x$ -axis at $-\infty$ and $+\infty$ and denote them by $1,2,\ldots,n$ according to their order from top to bottom at $-\infty$ . Let $f:\{1,2,\ldots,n\}\rightarrow\{1,2,\ldots,n\}$ denote their order at $+\infty$ , that is, $f(i)$ is the location of $i$ in the order of the curves from top to bottom at $+\infty$ .

If $f$ is the identity function, then every pair of curves either touch or cross at an even number of points. In such a case, every two curves that cross at $k^{\prime}<k$ points, can be redrawn very close to one of their crossing points such that they cross at $k-k^{\prime}$ new crossing points. This way we get exactly $k$ crossing points between every pair of non-touching curves. Otherwise, if $f$ is not the identity function, then we can redraw two curves that cross an odd number of times such that they cross an even number of times and repeat this process until $f$ becomes the identity function. Indeed, let $i$ and $j$ be two curves such that $i<j$ and $f(i)>f(j)$ . If there are several such pairs we choose a “closest” one, that is, one which minimizes the difference $f(i)-f(j)$ . Note that there is no curve $l$ such that $f(i)>f(l)>f(j)$ , for otherwise we must have both $l<i$ and $j<l$ (or else $(i,l)$ or $(l,j)$ would be a “reversed” pair closer than $(i,j)$ ) which is impossible since $i<j$ . Therefore, $f(i)=f(j)+1$ and it follows that we can redraw $i$ and $j$ such that they cross at an additional point. $\hfill\blacktriangleleft$

5 An Erdős-Simonovits-type theorem

In this section we prove Theorems 9 and 10 and discuss some of their applications and connections to other graph theoretic results. For a graph $G=(V,E)$ we denote by $\overline{d}(G)=2|E|/|V|$ the average degree in $G$ . The subgraph induced by a subset of vertices $U\subseteq V$ is denoted by $G[U]$ . For a vertex $v\in V$ we denote by $N_{G}(v)$ (or simply $N(v)$ when the context is clear) the neighbors of $v$ in $G$ . The (open) bineighborhood of two vertices $v$ and $u$ is equal to $(N_{G}(v)\cup N_{G}(u))\setminus\{u,v\}$ . Assume henceforth that $G$ is bipartite and recall that for a nonnegative and nondecreasing function $f:\mathbb{R}\rightarrow\mathbb{R}$ we say that two vertices $u$ and $v$ have $f$ -sparse sub-bineighborhoods if for every two disjoint subsets $U\subseteq N_{G}(u)\setminus\{v\}$ and $V\subseteq N_{G}(v)\setminus\{u\}$ it holds that $|E(G(U,V))|\leq f(|U\cup V|)$ , where $G(U,V)$ is the bipartite subgraph $(U\cup V,\{(u,v)\in E(G)\mid u\in U\textrm{ and }v\in V\})$ . Theorem 9 will follow from the next result.

Theorem 25.

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be a nonnegative and nondecreasing function and let $G=(A\cup B,E)$ be an $n$ -vertex bipartite graph with $\overline{d}(G)\geq 16$ .

(i)

If every pair of vertices in $G$ has $f$ -sparse sub-bineighborhoods, then $(\overline{d}(G))^{3}\leq 2^{11}nf(2\overline{d}(G))$ .
(ii)

If every pair of adjacent vertices has $f$ -sparse sub-bineighborhoods and $|E|\geq 25n^{3/2}$ , then $(\overline{d}(G))^{3}\leq 2^{20}nf(2\overline{d}(G))$ .

Proof.

Set $m=|E|$ and let $d=\overline{d}(G)=2m/n$ be the average degree of $G$ . We first replace $G$ with a graph $G^{\prime}$ in which the degree of every vertex is roughly the average degree (while maintaining the $f$ -sparseness property): Go over the vertices of $G$ in an arbitrary order and replace each vertex $v$ such that $\deg(v)>d$ by $\lfloor\deg(v)/d\rfloor$ vertices of degree $d$ and possibly one vertex of a smaller degree. The neighbors of $v$ are connected to the vertices that replace $v$ in an arbitrary manner which satisfies this property. Observe that the resulting graph still has $f$ -sparse sub-bineighborhoods for every pair of (adjacent) vertices, since each sub-neighborhood of a vertex in the new graph cannot contain two vertices that correspond to the same original vertex. Thus, every sub-neighborhood in the new graph corresponds to a sub-neighborhood in $G$ . Furthermore, since $d=2m/n$ , the number of vertices in the new graph is at most $\sum_{v\in A\cup B}(\lfloor\deg_{G}(v)/d\rfloor+1)\leq 2n$ . Because the number of edges remains the same, the average degree of this graph is at least $d/2$ .

Next, we repeatedly remove vertices of degree smaller than $d/8$ until no such vertices remain. We claim that at least $m/2$ edges remain after this step. Indeed, suppose for contradiction that less than $m/2$ edges remain and denote by $x$ the number of vertices that were removed. Then at most $xd/8$ edges were removed, therefore $xd/8>m/2=2nd/8$ which is impossible since $x\leq 2n$ . Denote by $G^{\prime}=(A^{\prime}\cup B^{\prime},E^{\prime})$ the resulting graph and note that $|A^{\prime}\cup B^{\prime}|\leq 2n$ , $|E^{\prime}|\geq m/2$ and the degree of every vertex in $G^{\prime}$ is at least $d/8$ and at most $d$ . Observe also that $|A^{\prime}\cup B^{\prime}|\geq 2|E^{\prime}|/d\geq m/d=n/2$ . Furthermore, $G^{\prime}$ still has the $f$ -sparse sub-bineighborhoods property, since this property is maintained when deleting a vertex.

Considering (i), for each pair of vertices $a\in A^{\prime}$ and $b\in B^{\prime}$ the number of edges in the subgraph of $G^{\prime}$ induced by the union of their open bineighborhoods is at most $f(2d)$ . Therefore we have $\sum_{a\in A^{\prime},b\in B^{\prime}}|E(G^{\prime}[(N_{G^{\prime}}(a)% \setminus\{b\})\cup(N_{G^{\prime}}(b)\setminus\{a\}])|\leq\binom{2n}{2}f(2d)% \leq 2n^{2}f(2d)$ . Note that every edge $(a,b)\in E^{\prime}$ is counted in this sum for every pair $a^{\prime}\in A^{\prime}$ and $b^{\prime}\in B^{\prime}$ such that $a\in N_{G^{\prime}}(b^{\prime})\setminus\{a^{\prime}\}$ and $b\in N_{G^{\prime}}(a^{\prime})\setminus\{b^{\prime}\}$ . Since $a$ (resp., $b$ ) has at least $\frac{d}{8}-1\geq\frac{d}{16}$ neighbors different from $b$ (resp., $a$ ), it follows that $(a,b)$ is counted at least $d^{2}/256$ times in the above sum (here we used the assumption $d\geq 16$ ). Therefore, $nd/2=m=|E|\leq 2|E^{\prime}|\leq 2^{10}n^{2}f(2d)/d^{2}$ and thus $d^{3}\leq 2^{11}nf(2d)$ .

Considering (ii), we have $d\geq 50n^{1/2}$ since $m\geq 25n^{3/2}$ . Assume w.l.o.g. that $|B^{\prime}|\geq|A^{\prime}|$ and therefore $|B^{\prime}|\geq n/4$ and $|A^{\prime}|\leq n$ . Let $\#K_{2,1}$ be the number of $K_{2,1}$ ’s in $G^{\prime}$ with two vertices in $A^{\prime}$ and let $\#K_{2,2}$ be the number of $K_{2,2}$ ’s in $G^{\prime}$ . Then,

\#K_{2,2}=\frac{1}{4}\sum_{a\in A^{\prime},b\in B^{\prime},(a,b)\in E^{\prime}% }|E(G^{\prime}[(N_{G^{\prime}}(a)\setminus\{b\})\cup(N_{G^{\prime}}(b)% \setminus\{a\}])|\leq\frac{m}{4}f(2d)=\frac{dn}{8}f(2d).

On the other hand, denoting $s_{a,a^{\prime}}=|N_{G^{\prime}}(a)\cap N_{G^{\prime}}(a^{\prime})|$ for two distinct vertices $a,a^{\prime}\in A^{\prime}$ we have $\#K_{2,1}=\sum_{a\neq a^{\prime}\in A^{\prime}}s_{a,a^{\prime}}$ and:

	$\displaystyle\#K_{2,2}$	$\displaystyle=\sum_{a\neq a^{\prime}\in A^{\prime}}\binom{s_{a,a^{\prime}}}{2}% =\frac{1}{2}\sum_{a\neq a^{\prime}\in A^{\prime}}(s_{a,a^{\prime}}^{2}-s_{a,a^% {\prime}})$
		$\displaystyle\geq\frac{(\#K_{2,1})^{2}}{2\binom{\|A^{\prime}\|}{2}}-\frac{\#K_{2% ,1}}{2}\geq\frac{(\#K_{2,1})^{2}}{2\binom{n}{2}}-\frac{\#K_{2,1}}{2},$

where the second to last inequality follows from Cauchy’s inequality. For $\#K_{2,1}$ we have the following lower bound:

\#K_{2,1}=\sum_{a\neq a^{\prime}\in A^{\prime}}s_{a,a^{\prime}}=\sum_{b\in B^{% \prime}}\binom{\deg(b)}{2}\geq\frac{n}{4}\binom{d/8}{2}\geq nd^{2}/2^{11}\geq n% ^{2},

where we used double-counting by the vertex from $B^{\prime}$ for the $K_{2,1}$ ’s and the inequalities $|B^{\prime}|\geq n/4$ and $d\geq 50n^{1/2}$ . Combining the inequalities above we get:

	$\displaystyle\frac{dnf(2d)}{8}$	$\displaystyle\geq\#K_{2,2}\geq\frac{(\#K_{2,1})^{2}}{n^{2}}-\frac{\#K_{2,1}}{2% }\geq\frac{(\#K_{2,1})^{2}}{n^{2}}-\frac{(\#K_{2,1})^{2}}{2n^{2}}=\frac{(\#K_{% 2,1})^{2}}{2n^{2}}$
		$\displaystyle\geq\frac{n^{2}d^{4}}{2^{22}\cdot 2n^{2}}=\frac{d^{4}}{2^{23}}.$

This implies that $d^{3}\leq 2^{20}nf(2d)$ , as claimed. $\hfill\blacktriangleleft$

Using Theorem 25 we can now prove Theorem 9 which we restate for convenience. See 9

Proof.

Recall that every graph contains a bipartite subgraph whose size is at least half of the size of the graph. Let $G^{\prime}=(A^{\prime}\cup B^{\prime},E^{\prime})$ be such a bipartite subgraph of $G$ , where $|E^{\prime}|\geq|E(G)|/2$ , and let $n=|V(G)|$ and $d^{\prime}=\overline{d}(G^{\prime})$ . If every pair of vertices in $G$ has $f$ -sparse sub-bineighborhoods, then the same holds for $G^{\prime}$ and it follows from Theorem 25 that $d^{\prime 3}\leq 2^{11}nf(2d^{\prime})=O(nd^{\prime 2-\alpha})$ . Thus, $d^{\prime}\leq O(n^{1/(\alpha+1)})$ and the upper bound follows.

If $0<\alpha\leq 1$ and every pair of adjacent vertices has $f$ -sparse sub-bineighborhoods, then we may assume that $|E^{\prime}|\geq 25n^{3/2}$ for otherwise the theorem trivially holds. Therefore, by Theorem 25 we have $d^{\prime 3}\leq 2^{20}nf(2d^{\prime})=O(nd^{\prime 2-\alpha})$ and $d^{\prime}\leq O(n^{1/(\alpha+1)})$ as before. $\hfill\blacktriangleleft$

For the lower bound we show that an appropriate random bipartite graph meets the criteria with positive probability, the proof can be found in the full version of this paper [2].

Remarks

$\blacksquare$

The proof of Theorem 9 is quite similar to the proof of Theorem 8 in [10]. In both cases, one first makes the graph close to being regular and then uses double-counting, however, in the case of Theorem 8 the first part requires more effort. Chronologically, we first proved the first part of Theorem 9 which was needed for the proof of Theorem 3, only later did we learn about Theorem 8 and used it to prove the second part of Theorem 9.
$\blacksquare$

It would be interesting to determine whether Theorem 9 holds when one assumes sparsity of the subgraph induced by the bineighborhood of every pair of (adjacent) vertices instead of assuming sparsity of subgraphs induced by each of their sub-bineighborhoods. We note that the first part of the proof of Theorem 9 does not go through in such a case. Also, $f$ -sparse bineighborhoods do not imply $f$ -sparse sub-bineighborhoods.
$\blacksquare$

Theorem 9 might find other applications, e.g., in other scenarios where it can be combined with Theorem 13. Here is one example. For a graph $H$ let $\mbox{ex}_{\textrm{cr}}(n,H)$ be the maximum number of edges in a topological graph on $n$ vertices with no self-intersecting copy $H$ . Note that $\mbox{ex}(n,H)\leq\mbox{ex}_{\textrm{cr}}(n,H)$ and if $H$ is non-planar then $\mbox{ex}(n,H)=\mbox{ex}_{\textrm{cr}}(n,H)$ . In [16] Theorem 13 is used to show that $\mbox{ex}_{\textrm{cr}}(n,C_{4})=O(n^{3/2})$ (and this is tight). Using Theorem 9 this immediately implies:

Corollary 26.

$\mbox{ex}_{\textrm{cr}}(K_{2,3})=O(n^{5/3})$ and $\mbox{ex}_{\textrm{cr}}(n,K_{3,3}^{-})=O(n^{5/3})$ where $K_{3,3}^{-}$ is the complete bipartite graph on $3+3$ vertices minus one edge.

References

[1] Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and Rebeka Raffay. The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles. In Oswin Aichholzer and Haitao Wang, editors, 41st International Symposium on Computational Geometry (SoCG 2025), volume 332 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:14, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2025.2.
[2] Eyal Ackerman and Balázs Keszegh. On the maximum number of tangencies among $1$ -intersecting curves, 2026. arXiv:2603.11885.
[3] Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi. On tangencies among planar curves with an application to coloring L-shapes. European Journal of Combinatorics, 121:103837, 2024. doi:10.1016/j.ejc.2023.103837.
[4] Eyal Ackerman and Balázs Keszegh. On the number of tangencies among 1-intersecting $x$ -monotone curves. European Journal of Combinatorics, 118:103929, 2024. doi:10.1016/j.ejc.2024.103929.
[5] Pankaj K. Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, and Shakhar Smorodinsky. Lenses in arrangements of pseudo-circles and their applications. J. ACM, 51(2):139–186, 2004. doi:10.1145/972639.972641.
[6] Itay Ben-Dan and Rom Pinchasi. personal communication.
[7] Jon Bentley and Thomas Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28(9):643–647, 1979. doi:10.1109/TC.1979.1675432.
[8] Peter Brass, William O. J. Moser, and János Pach. Research problems in discrete geometry. Springer, 2005.
[9] Jordan S. Ellenberg, Jozsef Solymosi, and Joshua Zahl. New bounds on curve tangencies and orthogonalities. Discrete Analysis, November 4 2016. doi:10.19086/da.990.
[10] P. Erdős and M. Simonovits. Some extremal problems in graph theory. In P. Erdős, A. Rényi, and V. T. Sós, editors, Combinatorial Theory and its Applications, I, volume 4 of Colloquia Mathematica Societatis János Bolyai, pages 377–390. North-Holland, Amsterdam, 1970. Proc. Colloq., Balatonfüred (Hungary), 1969. URL: https://users.renyi.hu/˜miki/1970-22ErdSimCube.pdf.
[11] Pál Erdős and Branko Grünbaum. Osculation vertices in arrangements of curves. Geometriae Dedicata, 1(4):322–333, 1973. doi:10.1007/BF00147765.
[12] István Fáry. On straight line-representations of planar graphs. Acta Scientiarum Mathematicarum, 12(182-192):229, 1948.
[13] Branko Grünbaum. Arrangements and spreads. Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 10. American Mathematical Society, Providence, R.I., 1972.
[14] Péter Györgyi, Bálint Hujter, and Sándor Kisfaludi-Bak. On the number of touching pairs in a set of planar curves. Computational Geometry, 67:29–37, 2018. doi:10.1016/j.comgeo.2017.10.004.
[15] Sariel Har-Peled. Constructing planar cuttings in theory and practice. SIAM Journal on Computing, 29(6):2016–2039, 2000. doi:10.1137/S0097539799350232.
[16] Barnabás Janzer, Oliver Janzer, Abhishek Methuku, and Gábor Tardos. Tight bounds for intersection-reverse sequences, edge-ordered graphs and applications. Journal of the London Mathematical Society, 112(4), October 2025. doi:10.1112/jlms.70324.
[17] Balázs Keszegh and Dömötör Pálvölgyi. The number of tangencies between two families of curves. Combinatorica, 43(5):939–952, October 2023. doi:10.1007/s00493-023-00041-8.
[18] T. Kővári, V. Sós, and P. Turán. On a problem of K. Zarankiewicz. Colloquium Mathematicae, 3(1):50–57, 1954. URL: http://eudml.org/doc/210011.
[19] Adam Marcus and Gábor Tardos. Intersection reverse sequences and geometric applications. J. Comb. Theory, Ser. A, 113(4):675–691, 2006. doi:10.1016/j.jcta.2005.07.002.
[20] János Pach. personal communication.
[21] János Pach and Pankaj K. Agarwal. Combinatorial Geometry, chapter 11, pages 177–178. John Wiley and Sons Ltd, 1995. doi:10.1002/9781118033203.ch11.
[22] János Pach, Natan Rubin, and Gábor Tardos. A crossing lemma for Jordan curves. Advances in Mathematics, 331:908–940, 2018. doi:10.1016/j.aim.2018.03.015.
[23] János Pach and Micha Sharir. On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm. SIAM Journal on Computing, 20(3):460–470, 1991. doi:10.1137/0220029.
[24] János Pach and Micha Sharir. Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, volume 152 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2009. doi:10.1090/surv/152.
[25] János Pach, Andrew Suk, and Miroslav Treml. Tangencies between families of disjoint regions in the plane. Comput. Geom., 45(3):131–138, 2012. doi:10.1016/j.comgeo.2011.10.002.
[26] Rom Pinchasi and Radoš Radoičić. On the number of edges in a topological graph with no self-intersecting cycle of length 4. In János Pach, editor, Towards a Theory of Geometric Graphs, volume 342 of Contemporary Mathematics, pages 233–234. American Mathematical Society, 2004.
[27] Micha Sharir and Pankaj K. Agarwal. Davenport–Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.

[bib.bib1] [1] Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and Rebeka Raffay. The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles. In Oswin Aichholzer and Haitao Wang, editors, 41st International Symposium on Computational Geometry (SoCG 2025), volume 332 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:14, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2025.2.

[bib.bib2] [2] Eyal Ackerman and Balázs Keszegh. On the maximum number of tangencies among $1$ -intersecting curves, 2026. arXiv:2603.11885.

[bib.bib3] [3] Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi. On tangencies among planar curves with an application to coloring L-shapes. European Journal of Combinatorics, 121:103837, 2024. doi:10.1016/j.ejc.2023.103837.

[bib.bib4] [4] Eyal Ackerman and Balázs Keszegh. On the number of tangencies among 1-intersecting $x$ -monotone curves. European Journal of Combinatorics, 118:103929, 2024. doi:10.1016/j.ejc.2024.103929.

[bib.bib5] [5] Pankaj K. Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir, and Shakhar Smorodinsky. Lenses in arrangements of pseudo-circles and their applications. J. ACM, 51(2):139–186, 2004. doi:10.1145/972639.972641.

[bib.bib6] [6] Itay Ben-Dan and Rom Pinchasi. personal communication.

[bib.bib7] [7] Jon Bentley and Thomas Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Transactions on Computers, C-28(9):643–647, 1979. doi:10.1109/TC.1979.1675432.

[bib.bib8] [8] Peter Brass, William O. J. Moser, and János Pach. Research problems in discrete geometry. Springer, 2005.

[bib.bib9] [9] Jordan S. Ellenberg, Jozsef Solymosi, and Joshua Zahl. New bounds on curve tangencies and orthogonalities. Discrete Analysis, November 4 2016. doi:10.19086/da.990.

[bib.bib10] [10] P. Erdős and M. Simonovits. Some extremal problems in graph theory. In P. Erdős, A. Rényi, and V. T. Sós, editors, Combinatorial Theory and its Applications, I, volume 4 of Colloquia Mathematica Societatis János Bolyai, pages 377–390. North-Holland, Amsterdam, 1970. Proc. Colloq., Balatonfüred (Hungary), 1969. URL: https://users.renyi.hu/˜miki/1970-22ErdSimCube.pdf.

[bib.bib11] [11] Pál Erdős and Branko Grünbaum. Osculation vertices in arrangements of curves. Geometriae Dedicata, 1(4):322–333, 1973. doi:10.1007/BF00147765.

[bib.bib12] [12] István Fáry. On straight line-representations of planar graphs. Acta Scientiarum Mathematicarum, 12(182-192):229, 1948.

[bib.bib13] [13] Branko Grünbaum. Arrangements and spreads. Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 10. American Mathematical Society, Providence, R.I., 1972.

[bib.bib14] [14] Péter Györgyi, Bálint Hujter, and Sándor Kisfaludi-Bak. On the number of touching pairs in a set of planar curves. Computational Geometry, 67:29–37, 2018. doi:10.1016/j.comgeo.2017.10.004.

[bib.bib15] [15] Sariel Har-Peled. Constructing planar cuttings in theory and practice. SIAM Journal on Computing, 29(6):2016–2039, 2000. doi:10.1137/S0097539799350232.

[bib.bib16] [16] Barnabás Janzer, Oliver Janzer, Abhishek Methuku, and Gábor Tardos. Tight bounds for intersection-reverse sequences, edge-ordered graphs and applications. Journal of the London Mathematical Society, 112(4), October 2025. doi:10.1112/jlms.70324.

[bib.bib17] [17] Balázs Keszegh and Dömötör Pálvölgyi. The number of tangencies between two families of curves. Combinatorica, 43(5):939–952, October 2023. doi:10.1007/s00493-023-00041-8.

[bib.bib18] [18] T. Kővári, V. Sós, and P. Turán. On a problem of K. Zarankiewicz. Colloquium Mathematicae, 3(1):50–57, 1954. URL: http://eudml.org/doc/210011.

[bib.bib19] [19] Adam Marcus and Gábor Tardos. Intersection reverse sequences and geometric applications. J. Comb. Theory, Ser. A, 113(4):675–691, 2006. doi:10.1016/j.jcta.2005.07.002.

[bib.bib20] [20] János Pach. personal communication.

[bib.bib21] [21] János Pach and Pankaj K. Agarwal. Combinatorial Geometry, chapter 11, pages 177–178. John Wiley and Sons Ltd, 1995. doi:10.1002/9781118033203.ch11.

[bib.bib22] [22] János Pach, Natan Rubin, and Gábor Tardos. A crossing lemma for Jordan curves. Advances in Mathematics, 331:908–940, 2018. doi:10.1016/j.aim.2018.03.015.

[bib.bib23] [23] János Pach and Micha Sharir. On vertical visibility in arrangements of segments and the queue size in the Bentley-Ottmann line sweeping algorithm. SIAM Journal on Computing, 20(3):460–470, 1991. doi:10.1137/0220029.

[bib.bib24] [24] János Pach and Micha Sharir. Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, volume 152 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2009. doi:10.1090/surv/152.

[bib.bib25] [25] János Pach, Andrew Suk, and Miroslav Treml. Tangencies between families of disjoint regions in the plane. Comput. Geom., 45(3):131–138, 2012. doi:10.1016/j.comgeo.2011.10.002.

[bib.bib26] [26] Rom Pinchasi and Radoš Radoičić. On the number of edges in a topological graph with no self-intersecting cycle of length 4. In János Pach, editor, Towards a Theory of Geometric Graphs, volume 342 of Contemporary Mathematics, pages 233–234. American Mathematical Society, 2004.

[bib.bib27] [27] Micha Sharir and Pankaj K. Agarwal. Davenport–Schinzel Sequences and Their Geometric Applications. Cambridge University Press, New York, 1995.

On the Maximum Number of Tangencies Among 1-Intersecting Curves

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Conjecture 1 (Pach [20]).

Theorem 2 ( [17]).

Theorem 3.

Theorem 4.

Theorem 5.

Theorem 6.

Theorem 7.

1.1 A graph-theoretic theorem

Theorem 8 ([10, Theorem 2]).

Theorem 9.

Theorem 10.

1.2 Related work

Organization

2 Notations and Tools

Theorem 11 (Cutting Lemma for x-monotone curves [15, Proposition 2.11]).

Theorem 12 (Kővári-Sós-Turán Theorem [18]).

Theorem 13 ([16]).

3 Arbitrary 𝟏-intersecting curves

Theorem 14.

Proof.

Proposition 15.

Proof.

Proposition 16.

Proof.

Lemma 17 ([26, Lemma 1]).

Corollary 18.

Proof.

Corollary 19.

Proof.

Proof.

Theorem 3. [Restated, see original statement.]

Proof.

4 Tangencies among 𝒙-monotone curves

4.1 Bi-infinite 𝒌-intersecting 𝒙-monotone curves

Conjecture 20.

Observation 21.

Proposition 22.

Proof.

Proposition 23.

Proof.

Proposition 24.

Proof.

5 An Erdős-Simonovits-type theorem

Theorem 25.

Proof.

Proof.

Remarks

Corollary 26.

References

On the Maximum Number of Tangencies Among $1$ -Intersecting Curves

Theorem 11 (Cutting Lemma for $x$ -monotone curves [15, Proposition 2.11]).

3 Arbitrary $1$ -intersecting curves

4 Tangencies among $𝒙$ -monotone curves

4.1 Bi-infinite $𝒌$ -intersecting $𝒙$ -monotone curves