# An algorithm for estimating the crossing number of dense graphs, and
continuous analogs of the crossing and rectilinear crossing numbers

Oriol Solé Pi111Department of Mathematics, Massachusetts Institute of
Technology. Email<EMAIL_ADDRESS>
###### Abstract

We present a deterministic $n^{2+o(1)}$-time algorithm that approximates the
crossing number of any graph $G$ of order $n$ up to an additive error of
$o(n^{4})$. We also provide a randomized polynomial-time algorithm that
constructs a drawing of $G$ with $\text{cr}(G)+o(n^{4})$ crossings. These
results are made interesting by the well known fact that every dense
$n$-vertex graph has crossing number $\Theta(n^{4})$. Our work builds on a
technique developed by Fox, Pach and Súk [18], who obtained very similar
results for the rectilinear crossing number.

The results in [18] and in this paper imply that the (normalized) crossing and
rectilinear crossing numbers are estimable parameters. Motivated by this, we
introduce two graphon parameters, the crossing density and the rectilinear
crossing density, and then we prove that, in a precise sense, these are the
correct continuous analogs of the crossing and rectilinear crossing numbers of
graphs.

##  1 Introduction

We work only with finite, simple and undirected graphs.

Let $G=(V,E)$ be a graph. A drawing of $G$ is a representation in which the
vertices are mapped to distinct points on the plane and the edges are
represented by simple continuous curves. We further assume that no edge goes
through a vertex other than its endpoints, no two edges are tangent at any
point, and no three of them have an interior point in common. A crossing is a
common interior point of two edges in a drawing. The crossing number of $G$,
denoted by $\mathop{\mathrm{cr}}(G)$, is the minimum number of crossing points
between edges when the minimum is taken over all drawings of $G$. Note that
any drawing of $G$ with $\mathop{\mathrm{cr}}(G)$ crossings has the additional
property that no two edges cross more than once and no two adjacent edges
cross. A straight-line drawing of $G$ is a drawing such that each edge is
represented by a segment joining the corresponding endpoints. The rectilinear
crossing number of $G$, $\overline{\mathop{\mathrm{cr}}}(G)$, is the least
number of crossings amongst all straight-line drawings of $G$. Clearly,
$\mathop{\mathrm{cr}}(G)\leq\overline{\mathop{\mathrm{cr}}}(G)$, and it is
known that there are graphs for which the inequality is strict (a rather
surprising example was obtained by Bienstock and Dean [8], who constructed
graphs with crossing number $4$ but arbitrarily large rectilinear crossing
number).

The crossing number and the rectilinear crossing number have been studied
extensively, and we refer the reader to the surveys of Schaefer [37] and Pach
and Tóth [35] for a review of the existing literature and several interesting
questions. One of the central open problems in the area is the determination
of the asymptotic behaviour of $\overline{\mathop{\mathrm{cr}}}(K_{n})$; while
it is well known that the limit

$\lim_{n\rightarrow\infty}\frac{\overline{\mathop{\mathrm{cr}}}(K_{n})}{\binom{n}{4}}$

exists (cf. [38]), determining it has proven to be very challenging.
Currently, the best known bounds place this quantity between $0.379972$ and
$0.380473$, these are due to Ábrego et al. [1] and Fabila-Monroy and López
[17], respectively. For the crossing number, it is conjectured that

$\mathop{\mathrm{cr}}(K_{n})=\frac{1}{4}\lfloor\frac{n}{2}\rfloor\lfloor\frac{n-1}{2}\rfloor\lfloor\frac{n-2}{2}\rfloor\lfloor\frac{n-3}{2}\rfloor,$

and drawings with this number of crossings have been known for several years
(c.f. Moon [33], Guy [23]), but a proof that this is optimal has remained
elusive. Still, the limit

$\lim_{n\rightarrow\infty}\frac{\mathop{\mathrm{cr}}(K_{n})}{\binom{n}{4}}$

exists and, by the result we just mentioned, is bounded from above by $3/8$.
An interesting consequence of this is that this limit differs from the one for
rectilinear crossing numbers. The asymptotic behaviours of
$\mathop{\mathrm{cr}}(K_{m,n})$ and $\overline{\mathop{\mathrm{cr}}}(K_{m,n})$
are not completely understood either (see [37] and the references therein).
The rectilinear crossing number of $K_{n}$ is closely related to $k$-sets and
$k$-edges222Given a finite set $P$ of points on the plane, a $k$-set is a
$k$-element subset $S\subset P$ for which there exists a half-plane $H$ with
$H\cap P=S$, and a $k$-edge consists of a pair of points $p,q\in P$ such that
one of the closed half-planes determined by the line trough $p$ and $q$
contains exactly $k$ points of $P$. [31, 4], as well as to Sylvester’s four
point problem333Sylvester’s four point problem asks for the probability that
four points chosen at random from a region $R$ of the plane lie in convex
position. When $R$ is the whole plane, there are a few natural distributions
from which one can choose the points; this led to some different answers being
published. See [36] for an overview of the history of the problem. [38]. We
shall come back to the later of this connections in section 4.

Moving on to the computational aspects of the problem, computing the crossing
number is known to be NP-complete [20], while determining the rectilinear
crossing numbers is complete for the existential theory of reals [7], and
hence NP-hard. For any fixed $k$, there is a linear time algorithm that
decides whether $\mathop{\mathrm{cr}}(G)\leq k$ (i.e., the crossing number is
fixed parameter tractable). In contrast, it is NP-hard to determine if
$\overline{\mathop{\mathrm{cr}}}(G)\leq k$ holds. A considerable amount of
work has been put into developing approximation algorithms for both
$\mathop{\mathrm{cr}}(G)$ and $\overline{\mathop{\mathrm{cr}}}(G)$. A graph
drawing technique of Bhatt and Leighton [6], in conjunction with the the
results of Leighton and Rao [27] on balanced cuts, can be combined to find, in
polynomial time, a straight-line drawing of any bounded degree $n$-vertex
graph $G$ with no more than $O(\log^{4}n(n+\mathop{\mathrm{cr}}(G))$
crossings. This was later improved to $O(\log^{3}n(n+\mathop{\mathrm{cr}}(G))$
by Even et al. [16], and then to $O(\log^{2}n(n+\mathop{\mathrm{cr}}(G))$ as a
result of the improved approximation algorithm for optimal balanced cuts by
Arora et al. [3]. The major drawback of the aforementioned algorithm is that
it provides no information in the case that $\mathop{\mathrm{cr}}(G)$ is at
most linear in $n$. It wasn’t until several years later that Chuzhoy [12],
using the edge planarization method444A subset of the edges of a graph is
called planarizing if deleting each of its elements results in a planar graph.
The method can be summarized as follows: First, one tries to find a small
planarizing set of edges and computes a planar drawing of the graph that we
get after deleting those edges. Then, the edges of the planarizing set are
carefully added to the drawing one by one until we obtain a drawing of the
original graph. from [14], found a polynomial-time $O(n^{9/10})$-approximation
algorithm for $\mathop{\mathrm{cr}}(G)$ for bounded degree graphs. Building
further on the edge planarization method, Kawarabayashi and Sidiropoulos [24,
25] improved the approximation ratio to $O(n^{1/2})$, and then Mahabadi and
Tan [13] found a randomized $O(n^{1/2-\delta})$-approximation algorithm, where
$\delta>0$ is a constant.

The celebrated crossing lemma, discovered simultaneously by Ajtai at al. [2]
and Leighton [26], tells us that
$\mathop{\mathrm{cr}}(G)\geq\frac{|E|^{3}}{64|V|^{2}}$, so long as $|E|\geq
4|V|$. An immediate consequence of this result is that if $G$ is dense (i.e.,
it has $\Omega(|V|^{2})$ edges) then both $\mathop{\mathrm{cr}}(G)$ and
$\overline{\mathop{\mathrm{cr}}}(G)$ are $\Omega(|V|^{4})$. Fox, Pach and Suk
[18] presented an algorithm that constructs a straight-line drawing of $G$
with $\overline{\mathop{\mathrm{cr}}}(G)+o(|V|^{4})$ crossings. More
precisely, they showed the following.

######  Theorem 1.1.

There is a deterministic $n^{2+o(1)}$-time algorithm that computes a straight-
line drawing of any given graph $n$-vertex graph $G$ with no more than

$\overline{\mathop{\mathrm{cr}}}(G)+O(n^{4}/(\log\log n)^{\delta})$

crossings, where $\delta$ is an absolute and positive constant.

Note that if $G$ is dense then the number of crossings in the drawing provided
by this algorithm is $(1+o(1))\overline{\mathop{\mathrm{cr}}}(G)$. In section
3, we obtain a similar result for the crossing number.

######  Theorem 1.2.

There exists a deterministic $n^{2+o(1)}$-time algorithm that for any given
graph $n$-vertex graph $G$ approximates $\mathop{\mathrm{cr}}(G)$ up to an
additive error of $O(n^{4}/(\log\log n)^{\delta^{\prime}})$. Furthermore,
there is a randomized polynomial-time algorithm that, with probability
$1-o(1)$, computes a drawing of $G$ with

$\mathop{\mathrm{cr}}(G)+O(n^{4}/(\log\log n)^{\delta^{\prime}})$

crossings. Here, $\delta^{\prime}$ denotes an absolute positive constant.

At a high level, this algorithm follows the strategy devised by Fox, Pach and
Suk for the proof of Theorem 1.1. The main novel ingredient in our proof is
Theorem 3.3, which provides a bound on the difference between the crossing
numbers of two graphs of the same order in terms of their cut distance.

A consequence of the results in [18] and in Section 3 of this paper is that
the (normalized) crossing and rectilinear crossing numbers are
estimable/testable parameters, in the sense of [9]. Motivated by this, in
Section 4 we define two graphon parameters, which we call the crossing density
and the rectilinear crossing density, by means of continuous analogs of the
notions of drawings and straight-line drawings of graphs. We show that both of
these parameters are continuous with respect to the cut norm and that, in a
precise sense, they behave as the limits of the crossing number and the
rectilinear crossing number of graphs. This fact is related to some of the
problems we mentioned earlier about the asymptotic behaviours of crossing
numbers. Some other properties of the crossing and rectilinear crossing
densities of graphons are also discussed in this section. We hope that our
results might prove useful in the study of crossing and rectilinear crossing
numbers of dense graphs. The basic definitions regarding graphons, cut
distance and estimable parameters are included in the following section.

##  2 Preliminaries

By an edge weighted graph, we mean a graph $G=(V,E)$ where each edge $(u,v)\in
E$ has a weight $w_{G}(u,v)\in[0,1]$ assigned to it. We write $w_{G}(u,v)=0$
whenever $(u,v)\notin E$. We shall work mostly with edge weighted graph, and
we often refer to them simply as graphs.

###  2.1 Crossing numbers of edge weighted graphs

Following [18], we extend the definitions of the crossing and the rectilinear
crossing numbers to edge weighted graphs. For an edge weighted graph $G(V,E)$
and a drawing $\mathcal{D}$ of $G$, let $C(\mathcal{D})$ denote the multi-set
of all pairs of edges that cross each other in the drawing, with the proper
multiplicity (i.e., if two edges cross each other at $k$ points then this pair
appears $k$ times in $C(\mathcal{D})$). Now, let

$\mathop{\mathrm{cr}}(G,\mathcal{D})=\sum_{(e_{1},e_{2})\in
C(\mathcal{D})}w_{G}(e_{1})w_{G}(e_{2})$

and define $\mathop{\mathrm{cr}}(G)$ as the least value of
$\mathop{\mathrm{cr}}(G,\mathcal{D})$ over all drawings of $G$. Similarly,
$\overline{\mathop{\mathrm{cr}}}(G)$ is the minimum of
$\mathop{\mathrm{cr}}(G,\mathcal{D})$ where $\mathcal{D}$ ranges over all
straight-line drawings of $G$. We say that a drawing $\mathcal{D}$ of $G$
attains $\mathop{\mathrm{cr}}(G)$ if
$\mathop{\mathrm{cr}}(G,\mathcal{D})=\mathop{\mathrm{cr}}(G)$, and that it
attains $\overline{\mathop{\mathrm{cr}}}(G)$ if it is a straight-line drawing
and $\mathop{\mathrm{cr}}(G,\mathcal{D})=\overline{\mathop{\mathrm{cr}}}(G)$.
A drawing such that no two edges cross more than once and no two adjacent
edges cross will be called simple. Although it is not as self evident as in
the unweighted case, one can readily show that there must exist a simple
drawing which attains $\mathop{\mathrm{cr}}(G)$. Note that, for unweighted
graphs, we can assign a weight of $1$ to every edge in order to recover the
definitions of crossing number and rectilinear crossing number provided in the
introduction.

We will need the following simple result, which fulfills the same role as
Lemma 2 in [18].

######  Theorem 2.1.

Let $G$ be an edge weighted graph on $n$ vertices such that the weight of each
edge can be represented using no more than $B$ bits. Then we can find a
drawing of $G$ that attains $\mathop{\mathrm{cr}}(G)$ in $2^{O(n^{4}\log
n)}+2^{O(n^{2})}B^{2}$ time.

###### Proof.

Given a set $C\subset\binom{E}{2}$, we can determine whether there is a simple
drawing $\mathcal{D}$ of $G$ with $C(\mathcal{D})=C$ in the following way: For
any given edge $e\in E$, there are less than $n^{2}!$ possible orders in which
the points where $e$ crosses the other edges may be arranged along the curve
representing $e$. For a fixed order of the crossings along every edge, we can
test whether it arises from an actual drawing of $G$ by placing a dummy vertex
at each crossing and then using a planarity testing algorithm. Thus, we can
test whether $C$ actually comes from a drawing in
$n^{2}!^{O(n^{2})}=2^{O(n^{4}\log n)}$ time.

If we are given $C(\mathcal{D})$, then we can compute
$\mathop{\mathrm{cr}}(G,\mathcal{D})$ in $O(n^{2}B^{2})$ time. Hence, we can
find a simple drawing $\mathcal{D}$ of $G$ that attains
$\mathop{\mathrm{cr}}(G)$ in $2^{O(n^{4}\log
n)}+O(2^{\binom{n}{2}}n^{2}B^{2})$ time. ∎

In order to study graphons in section 4, it will be convenient to have a
normalized version of the crossing and rectilinear crossing numbers. With this
in mind, for an edge weighted graph $G$ on $n$ vertices we define its crossing
density as $\mathop{\mathrm{cd}}(G)=\mathop{\mathrm{cr}}(G)/n^{4}$ and its
rectilinear crossing density as
$\overline{\mathop{\mathrm{cd}}}(G)=\overline{\mathop{\mathrm{cr}}}(G)/n^{4}$.

###  2.2 Cut distance and graphons

We assume some familiarity with the theory of graphons and convergent
sequences of dense graphs, but still include a few of the fundamental
definitions for the sake of completeness. We refer the reader to the book by
Lovász [29], which we follow rather closely during for the remainder of the
section, for on an in-depth treatment of the subject.

Let $G=(V,E)$ be an edge weighted graph. For any two subsets $S,T\subset V$,
let $E_{G}(S,T)$ denote the set of edges with one endpoint in $S$ and the
other one in $T$, and let $e_{G}(S,T)$ be the total weight of the elements of
$E_{G}(S,T)$, where edges with both endpoints in $S\cap T$ are counted twice.

Given a positive integer $m$, the m blow-up $G[m]$ of $G$ is the edge-weighted
graph obtained by replacing each vertex $v$ of $G$ by an independent set
$U_{v}$ with $m$ elements, and then setting the weight of every edge between
$U_{u}$ and $U_{v}$ (with $u\neq v$) to be $w_{G}(u,v)$. For any partition
$\mathcal{P}=\\{V_{1},V_{2},\dots,V_{n}\\}$ of $V$, let $G_{\mathcal{P}}$
denote the edge weighted graph with vertex set $V$ such that

$w_{G}(u,v)=\frac{e_{G}(V_{i},V_{j})}{|V_{i}||V_{j}|}$

whenever $u\in V_{i}$ and $v\in V_{j}$. Also, let $G/\mathcal{P}$ denote the
graph with vertex set $\\{1,2,\dots,n\\}$ and edge weights

$w_{G/\mathcal{P}}(i,j)=\frac{e_{G}(V_{i},V_{j})}{|V_{i}||V_{j}|}.$

The labeled cut distance between two edge weighted graphs $G_{1}$ and $G_{2}$
on the same finite vertex set $V$ is defined as

$d_{\square}(G_{1},G_{2})=\max_{S,T\subset
V}\frac{|e_{G_{1}}(S,T)-e_{G_{2}}(S,T)|}{|V|^{2}}.$

(Note: The reader who is only interested in the proof of Theorem 1.2 can now
skip to subsection 2.4.)

If $G_{1}$ and $G_{2}$ are are defined on possibly different $n$-element
vertex sets, then

$\widehat{\delta}_{\square}(G_{1},G_{2})=\min_{G_{1}^{\prime},G_{2}^{\prime}}d_{\square}(G_{1}^{\prime},G_{2}^{\prime}),$

where $G_{1}^{\prime}$ and $G_{2}^{\prime}$ range over all graphs with vertex
set $\\{1,2,\dots,n\\}$ which are isomorphic to $G_{1}$ and $G_{2}$,
respectively. We are ready to define the cut distance between two arbitrary
graphs. Given two edge weighted graphs $G_{1}$ and $G_{2}$ on $m$ and $n$
vertices, respectively, the cut distance between is given by

$\delta_{\square}(G_{1},G_{2})=\lim_{k\rightarrow\infty}\widehat{\delta}_{\square}(G_{1}[kn],G_{2}[km]),$

which can be shown to be well defined. The distance function
$\delta_{\square}$ is a pseudometric on the set of edge weighted graphs (it is
symmetric and satisfies the triangle inequality, but
$\delta_{\square}(G_{1},G_{2})$ does not imply that $G_{1}$ and $G_{2}$ are
isomorphic). We say that a sequence edge weighted graphs $G_{1},G_{2},\dots$
is convergent if it is Cauchy with respect to $\delta_{\square}$.

Throughout this paper, measurability is always with respect to the Lebesgue
$\sigma$-algebra, although working with Borel sets would not make a
significant difference. We denote the Lebesgue measure by $\lambda$. A kernel
is a symmetric measurable function $W:[0,1]^{2}\rightarrow\mathbb{R}$ (by
symmetric, we mean that $W(x,y)=W(y,x)$), the space of all kernels is denoted
by $\mathcal{W}$. A graphon is a kernel whose image is a subset of $[0,1]$, we
denote the space of graphons by $\mathcal{W}_{0}$.

The cut norm on $\mathcal{W}$ can be written as

$||W||_{\square}=\sup_{S,T\subseteq[0,1]}\left|\int_{S\times T}W(x,y)\ dx\
dy\right|,$

and the labeled cut distance between two kernels $W_{1}$ and $W_{2}$ is
$d_{\square}(W_{1},W_{2})=||W_{1}-W_{2}||_{\square}$. A measurable function
$\phi:[0,1]\rightarrow[0,1]$ is measure preserving if
$\lambda(S)=\lambda(\phi^{-1}(S))$ for every measurable $S\subseteq[0,1]$. For
a kernel $W$ and a measure preserving $\phi:[0,1]\rightarrow[0,1]$, let
$W^{\phi}$ denote the kernel with $W^{\phi}(x,y)=W(\phi(x),\phi(y))$. Now, for
any two kernels $W_{1}$ and $W_{2}$, the cut distance between them is defined
as

$\delta_{\square}(W_{1},W_{2})=\inf_{\phi}d_{\square}(W_{1},W_{2}^{\phi}),$

where $\phi$ ranges over all invertible measure preserving maps from $[0,1]$
to itself. The distance function $\delta_{\square}$ is a pseudometric on the
space $\mathcal{W}$, and two kernels $W_{1}$ and $W_{2}$ are said to be weakly
isomorphic if $\delta_{\square}(W_{1},W_{2})=0$. Thus, $\delta_{\square}$
induces a metric on the quotient space $\widetilde{\mathcal{W}_{0}}$ that
arises from $\mathcal{W}_{0}$ after identifying all classes of weakly
isomorphic graphons. One of the central results in the theory of graphons is
that $(\widetilde{\mathcal{W}_{0}},\delta_{\square})$ is compact (cf. [30]).

For every graph $G$ with vertices $v_{1},v_{2},\dots,v_{n}$, the graphon
$W_{G}$ is constructed by splitting $[0,1]$ into $n$ intervals
$I_{1},I_{2},\dots,I_{n}$ of measure $1/n$ and setting
$W_{G}(x,y)=w_{G}(v_{i},v_{j})$ for all $x\in I_{i},y\in I_{j}$. To be
precise, $W_{G}$ depends on both $G$ and an ordering of its vertices, but this
will not be an issue, since any two such graphons that arise from the same
graph are weakly isomorphic. Given any two edge weighted graphs $G_{1}$ and
$G_{2}$, we have that
$\delta_{\square}(G_{1},G_{2})=\delta_{\square}(W_{G_{1}},W_{G_{2}})$. For
every convergent graph sequence $G_{1},G_{2},\dots$, the graphons
$W_{G_{1}},W_{G_{2}},\dots$ converge, with respect to $\delta_{\square}$, to
some graphon $W$ (or, rather, to the class of $W$ in
$\widetilde{\mathcal{W}_{0}}$), and we say that the graph sequence converges
to $W$. Conversely, for every graphon $W$ there exists a convergent graph
sequence $G_{1},G_{2},\dots$ such that $W_{G_{1}},W_{G_{2}},\dots$ converges
to $W$ with respect to $d_{\square}$.

If $W$ is a kernel and $\mathcal{P}=\\{S_{1},S_{2},\dots,S_{n}\\}$ is a
partition of the unit interval into measurable sets, then $W_{\mathcal{P}}$
denotes the kernel such that

$W_{\mathcal{P}}(x,y)=\frac{1}{\lambda(S_{i})\lambda(S_{j})}\int_{S_{i}\times
S_{j}}W(x,y)\ dx\ dy$

whenever $x\in S_{i}$ and $y\in S_{j}$. Let
$\mathcal{P}_{1},\mathcal{P}_{2},\dots$ be a sequence of partitions of $[0,1]$
into measurable sets such that each pair of points of $[0,1]$ is separated by
all but a finite number of partitions of the sequence. Then, as $n$ goes to
infinity, $W_{\mathcal{P}_{n}}$ converges to $W$ almost everywhere for every
$W\in\mathcal{W}$.

Given a graph $F=(V,E)$ and a kernel $W$, let

$t(F,W)=\int_{[0,1]^{V}}\prod_{(u,v)\in E}W(x_{u},x_{v})\prod_{u\in V}dx_{u}.$

It is well known that two kernels $W_{1}$ and $W_{2}$ are weakly isomorphic if
and only if $t(F,W_{1})=t(F,W_{2})$ for every simple graph $F$. Moreover, a
sequence of kernels $W_{1},W_{2},\dots$ is convergent with respect to
$\delta_{\square}$ if and only if the limit
$\lim_{n\rightarrow\infty}t(F,W_{n})$ exists for every graph $F$.

###  2.3 Estimable parameters

By a graph parameter, we mean a function that assigns a real number to each
graphs (or edge weighted graph) and is constant on each isomorphism class. A
graph parameter $f$ is said to be estimable if there is another graph
parameter $g$, which we call a test parameter for $f$, with the following
property: For every $\varepsilon>0$ there exist an integer $k$ such that if
$G=(V,E)$ is a graph on at least $k$ vertices and $X$ is a random $k$-element
subset of $V$, then the probability that

$|f[X]-g(G[X])|>\varepsilon$

is at most $\varepsilon$ (here, $G[X]$ denotes the subgraph of $G$ that is
induced by $X$). It is no hard to see that if $f$ is estimable then can always
use $g=f$ (cf. [21, 9]). As shown by Borgs et al. [9], the following
properties are equivalent for every graph parameter $f$.

  1. (a)

$f$ is estimable.

  2. (b)

For every convergent sequence of graphs $G_{1},G_{2},\dots$, the sequence
$f(G_{1}),f(G_{2}),\dots$ converges as well.

  3. (c)

There exists a functional $\hat{f}$ on $\mathcal{W}_{0}$ that is continuous
with respect to the cut norm and such that $\hat{f}(W_{G})-f(G)\rightarrow 0$
as the number of vertices of $G$ goes to infinity.

If $f$ is estimable, then the functional $\hat{f}$ mentioned in (c) also
satisfies $\lim_{n\rightarrow\infty}f(G_{n})=f(W)$ whenever
$G_{1},G_{2},\dots$ converges to $W$ and the number of vertices of $G_{n}$
goes to infinity with $n$. We often refer to a functional on $\mathcal{W}_{0}$
as a graphon parameter. The authors of [9] also proved that the following
three properties together are equivalent to $f$ being estimable.

  1. (i)

For every $\varepsilon>0$ there exists an $\varepsilon^{\prime}$ such that any
two graphs $G_{1}$ and $G_{2}$ on the same vertex set with
$d_{\square}(G_{1},G_{2})<\varepsilon^{\prime}$ satisfy
$|f(G_{1})-f(G_{2})|<\varepsilon$.

  2. (ii)

For every graph $G$, $f(G[m])$ converges as $m$ goes to infinity.

  3. (iii)

$|f(G)-f(G\cup K_{1})|\rightarrow 0$ as the number of vertices of $G$ goes to
infinity.

This equivalence will come in handy in Section 3, since these properties are
easier to check than (b) and (c) above.

###  2.4 The Frieze-Kannan regularity lemma

Given a graph $G=(V,E)$, two sets of vertices $S,T\subset V$ and some
$\varepsilon>0$, we say that the pair $(S,T)$ is $\varepsilon$-regular if for
any $S^{\prime}\subset S$, $T^{\prime}\subset T$

$\left|\frac{e_{G}(S^{\prime},T^{\prime})}{|S^{\prime}||T^{\prime}|}-\frac{e_{G}(S,T)}{|S||T|}\right|\leq\varepsilon.$

According to Szemerédi’s regularity lemma [40], for every $\varepsilon>0$
there exists an $M(\varepsilon)$ such that for every graph we can find an
equitable partition of its vertices into no more than $M(\varepsilon)$ parts
with the property that all but at most an $\varepsilon$ fraction of the pairs
of parts are $\varepsilon$-regular. Szemerédi’s regularity lemma is one of the
most powerful tools in the study of dense graphs; unfortunately, it is not
very practical for algorithmic purposes, since $M(\varepsilon)$ grows
extremely fast as $\varepsilon$ goes to $0$ (see [22] for details about the
asymptotic behaviour of the optimal value of $M(\varepsilon)$). As was done by
the authors of [18], we circumvent this issue by means of a variant of the
regularity lemma developed by Frieze and Kannan [19]. Given a graph $G=(V,E)$,
we say that an equitable partition $\mathcal{P}=\\{V_{1},V_{2},\dots,V_{n}\\}$
of $V$ is a Frieze-Kannan $\varepsilon$-regular partition if
$d_{\square}(G,G_{\mathcal{P}})\leq\varepsilon$. The algorithmic version of
the Frieze-Kannan regularity lemma stated below is due to Dellamonica et al.
[15].

######  Lemma 2.2.

There exist a deterministic algorithm and an absolute constant $c$ such that
that for any $\varepsilon>0$ and any $n$-vertex graph $G=(V,E)$, computes a
Frieze-Kannan $\varepsilon$-regular partition of $G$ with no more than
$2^{\varepsilon^{-c}}$ classes in $2^{2^{\varepsilon^{-c}}}n^{2}$-time.

###  2.5 Cycle separators for planar graphs

The planar separator theorem [42, 28] states that for that every $n$-vertex
planar graph $G=(V,E)$ there exists a partition $V=A\sqcup B\sqcup C$ of its
vertex set such that $|B|=O(\sqrt{n})$, $|A|,|C|\leq 2n/3$, and there are no
edges between $A$ and $C$. This result is a cornerstone of the study of planar
graphs, and several generalizations and variants of it have been discovered
throughout the years. We will make use of the following version, due to Miller
[32].

######  Theorem 2.3.

Let $G$ be an embedded triangulation555By a triangulation we mean a maximal
planar graph. Every face of an embedded triangulation has precisely three
vertices on its boundary. with a non-negative weight assigned to each vertex
so that the total sum of the weights is $1$. Then, there exists a simple cycle
of length at most $L\sqrt{n}$ in $G$ such that the vertices that lie in its
interior have total weight at most $2/3$ and the same is true for those that
belong to its exterior. Here, $L$ is an absolute positive constant.

##  3 Estimating the crossing number

We say that a drawing $\mathcal{D}$ of an edge weighted graph $G$ is locally
optimal if the value of $\mathop{\mathrm{cr}}(G,\mathcal{D})$ can not be
reduced by erasing a single curve that represents an edge and then redrawing
the edge in some other way. If there are no edges of weight $0$, then any
locally optimal drawing is necessarily simple. We remark, however, that not
every locally optimal drawing attains the crossing number of the graph. This
section begins with a partitioning result about simple and locally optimal
graph drawings, which is somewhat similar in spirit to the classical cutting
lemma for line arrangements666The cutting lemma is a powerful tool in both
discrete and computational geometry. In its two dimensional version, it can be
stated as follows: Let $\mathcal{L}$ be a finite family of lines on the plane
and let $\varepsilon>0$. Then it is possible to subdivide the plane into
$O(1/\varepsilon^{2})$ convex regions, none of which is crossed by more than
$\varepsilon|\mathcal{L}|$ lines of $\mathcal{L}$. See [5, 10] for various
proofs of this result and its higher dimensional variants, as well as several
of their applications., and will play a crucial role in our proof that any two
graphs which are close with respect to $d_{\square}$ have similar crossing
numbers (Theorem 3.3).

######  Theorem 3.1.

Let $G$ be an $n$-vertex graph and let $\mathcal{D}$ be a simple and locally
optimal drawing of $G$. Then, for any $\varepsilon\in[0,1]$ the plane can be
subdivided into $O(1/\varepsilon^{2})$ closed, connected and interior disjoint
regions, each of which has the following properties:

  1. (I)

No vertex lies on its boundary.

  2. (II)

It contains at most $\lceil\varepsilon^{2}n\rceil$ vertices.

  3. (III)

Any vertex and any other point within it can be connected by a simple curve
that lies completely within the region, and whose relative interior, which
does not go through any vertex or crossing point of $\mathcal{D}$, has a total
of no more than $\varepsilon n^{2}$ intersection points with the curves that
represent the edges of $G$ that have no endpoint in that same region.

###### Proof.

If $\varepsilon\leq n^{-1/2}$, the subdivision can be obtained by splitting
the plane into $n+1$ regions, $n$ of which are very small and contain
precisely one vertex each. For $\varepsilon\geq 1$ we can use a single region,
so from now on we assume that $n^{-1/2}<\varepsilon<1$. A simple curve whose
relative interior does not pass through any vertex or crossing point of
$\mathcal{D}$ will be called clean.

We begin subdividing the plane into $O(1/\varepsilon^{2})$ closed, connected
and interior disjoint regions which contain no more than
$\lceil\varepsilon^{2}n\rceil$ vertices of $G$ each; this will be achieved
through repeated applications of Theorem 2.3. More precisely, we will build a
sequence $R_{0},R_{1},\dots,R_{t}$ of regions as follows: Let $R_{0}$ denote
the entire plane. By adding a dummy vertex at each crossing point,
$\mathcal{D}$ gives rise to an embedded planar graph, which can then be
transformed into an embedded triangulation $T_{0}$ by adding edges within each
face with more than three vertices on its boundary. Furthermore, this can be
done so that the degree in $T_{0}$ of every vertex of $G$ is upper bounded by
$3n$. Assign a weight of $1/n$ to every vertex of $G$ and a weight of $0$ to
every dummy vertex and apply Theorem 2.3 to $T_{0}$, thus obtaining a cycle
$C_{0}$ of length less than $Ln^{2}$ whose interior and exterior each contain
at most $2n/3$ vertices of $G$. Every vertex of $G$ that belongs to $C_{0}$
can be assigned to either the interior or the exterior of the cycle so that
the number of vertices in any of these two regions plus the number of vertices
that have been assigned to it is still no more than $2n/3$. By modifying the
cycle as depicted in Figure 1, we obtain a $C_{0}^{\prime}$ with less than
$Ln^{2}+n\cdot 3n$ nodes which contains no vertex of $G$. Denote the two
regions induced by this curve as $R_{1}$ and $R_{2}$; these contain at most
$2n/3$ vertices of $G$ each. For every $i$, $n_{i}$ will be used to denote the
number of vertices of $G$ that lie in $R_{i}$. Now, we iteratively apply the
procedure described below to subdivide each $R_{i}$ that contains
$n_{i}>\lceil\varepsilon^{2}n\rceil$ vertices of $G$ and has not yet been
subdivided into smaller regions.

If we restrict our attention to the boundary of $R_{i}$ and the portion of
$\mathcal{D}$ that lies inside this region, we get a planar graph. By adding
edges, this graph can be made into an embedded triangulation $T_{i}$ so that,
for every connected component of the complement of $R_{i}$, all the edges that
are drawn inside it are incident to the same vertex. Furthermore, the process
we are about to discuss will ensure that no vertex of $G$ lies on the boundary
of any of the $R_{j}$’s so, again, we can assume that the degree of every
vertex of $G$ in $T_{i}$ is upper bounded by $3n$. If we assign a weight of
$1/n_{i}$ to each of the vertices of $G$ that belong to $T_{i}$, then Theorem
2.3 yields a cycle $C_{i}$ of length at most $L\sqrt{m_{i}}$, where $m_{i}$
denotes the order of $T_{i}$. From now on, we will ignore the sections of
$C_{i}$ that are not contained in $R_{i}$; note that there is at most one of
these for every connected component of the complement of $R_{i}$. As we did
with $C_{0}$, $C_{i}$ can be modified slightly to obtain a curve (or, rather,
a collection of curves) with no more than $L\sqrt{m_{i}}+3n_{i}$ nodes that
does not go through any vertex of $G$ and such that both its exterior and
interior contain at most $2n_{i}/3$ vertices of $G$. One could try to use this
curve directly to split $R_{i}$ into smaller parts, but this could cause the
number of regions to blow up in the case that the curve shares many points
with the boundary of $R_{i}$. Thus, we first modify $C_{i}$ as shown in Figure
2 for every contiguous sequence of nodes and arcs that it shares with the
boundary of $R_{i}$ and connects two arcs that belong to the interior of
$R_{i}$. This results in a new $C_{i}^{\prime}$ with at most
$4(L\sqrt{m_{i}}+3n_{i})$ nodes, which is then used to split $R_{i}$ into two
smaller connected regions. After enough steps, we arrive at a subdivision of
the plane into closed, connected and interior disjoint regions that contain at
most $\lceil\varepsilon^{2}n\rceil$ vertices of $G$ each. These regions will
be referred to as fundamental regions from now on.

Figure 1: A small portion of $C_{0}$ has been highlighted in red. Assuming
that the vertex $v$ of $G$ has been assigned to the shaded region, we alter
the cycle around a small neighborhood of $v$ so that this point belongs to the
interior of the the shaded region defined by $C_{0}^{\prime}$. This increases
the number of nodes of the cycle by less than the degree of $v$ in $T_{0}$.
Figure 2: A section of $C_{i}$ (red) is contained in the boundary of $R_{i}$
and the two adjacent arcs (also in red) lie inside $R_{i}$. For every vertex
in this section, consider the edges of $G$ that are incident to it, lie in
$R_{i}$, and are contained in a curve that represents an edge of $G$ in
$\mathcal{D}$. Then, modify $C_{i}$ as shown above. Since no vertex of $G$
belongs to $C_{i}$, this increases the number of nodes in the curve by at most
three times the number of nodes that conform the original section of $C_{i}$.

It is not hard to see that the number of fundamental regions is
$O(1/\varepsilon^{2})$, but we will also require an upper bound on the total
number of arcs that conform their boundaries. This quantity is at most the
total number of nodes of the $C_{i}^{\prime}$’s. The argument that follows is
similar to the one used in the proof of Corollary 5 from [34]. The level of a
region $R_{i}$, which we denote by $l(R_{i})$, is defined as follows: If
$R_{i}$ is fundamental, then its level is $0$. Otherwise, its level is
obtained by adding $1$ to the largest of the levels of the two regions that
were created when splitting $R_{i}$ using $C_{i}^{\prime}$. The key
observation here is that any two $R_{i}$’s with the same level are interior
disjoint. This can be seen to imply that the orders of the $T_{i}$’s such that
$l(R_{i})=m$ for a fixed $m$ add up to

$O\left(n^{4}+\sum_{t,\ l(R_{t})<m}|C^{\prime}_{t}|\right).$

But it is not hard to check that the total complexity of the
$C_{t}^{\prime}$’s is $o(n^{4})$, so the above expression is $O(n^{4})$. On
the other hand, every $R_{i}$ with level $m\geq 1$ contains at least
$\lceil\varepsilon^{2}n\rceil(3/2)^{m-1}$ vertices of $G$, so there are at
most $\varepsilon^{-2}(2/3)^{m-1}$ such regions. Now, the Cauchy-Schwartz
inequality yields that the total complexity of the $C_{i}^{\prime}$’s in level
$m$ is at most

$\sum_{i,\ l(R_{i})=m}4(L\sqrt{m_{i}}+3n_{i})\leq
L^{\prime}\frac{n^{2}}{\varepsilon}\left(\frac{2}{3}\right)^{\frac{m-1}{2}}+12n^{2},$

where $L^{\prime}$ is an absolute constant. Adding over all levels, we arrive
at an upper bound of

$12n^{2}\cdot
l(R_{0})+\sum_{m=1}^{l(R_{0})}L^{\prime}\frac{n^{2}}{\varepsilon}\sqrt{\frac{2}{3}}^{(m-1)}=O(n^{2}/\varepsilon),$

since $l(R_{0})=O(\log\varepsilon^{-1})$. We remark that the bound on the
number of regions with level $m$ also implies that there are
$O(1/\varepsilon^{2})$ regions in total.

Next, we show how the fundamental regions can be further subdivided into
smaller parts that satisfy the requirements in the statement of the theorem.
Classify the edges of $G$ as light or heavy depending on whether or not they
are involved in less than $\varepsilon n^{2}/16$ crossings, respectively. By
applying the crossing lemma to the subgraph that contains only the light
edges, we get that the number of such edges is $O(\varepsilon^{1/2}n^{2})$.
For any two points $p$ and $q$ on the plane, define $d_{\mathcal{D}}(p,q)$ as
follows: If $p$ and $q$ belong to the same fundamental region and at least one
of them does not lie on its boundary, then let $d_{\mathcal{D}}$ be the least
positive integer such that there exists a clean curve which has endpoints $p$
and $q$, is contained in that region, and whose interior has at most that many
intersection points with the edges of the drawing. Otherwise, set
$d_{\mathcal{D}}(p,q)=\infty$. For any point $p$ on the plane and any positive
integer $k$, let $B_{\mathcal{D}}(p,k)$ be the set that consists of those
points $q$ such that $d_{\mathcal{D}}(p,q)\leq k$, and note that it is
connected. We say that an edge is encapsulated by $B_{\mathcal{D}}(p,k)$ if
both of its endpoints and all the points where it crosses another edge are
contained in $B_{\mathcal{D}}(p,k)$, and at least one of these points belongs
to the interior of this region.

######  Claim 3.2.

For every point $p$ that does not belong to the boundary of a fundamental
region, $B_{\mathcal{D}}(p,\varepsilon n^{2}/4)$ (which we assume is not the
whole plane) satisfies at least one of the properties below.

  1. 1.

It contains at least $\varepsilon n^{2}/16$ arcs of the boundary of the
fundamental region that encloses it.

  2. 2.

It contains one of the $C_{i}^{\prime}$’s in its entirety.

  3. 3.

At least $\varepsilon^{2}n^{4}/32^{2}$ crossing points of $\mathcal{D}$ lie in
its interior.

  4. 4.

It encapsulates at least $\varepsilon n^{2}/32$ light edges.

###### Proof.

First, we deal with the case where $B_{\mathcal{D}}(p,3\varepsilon n^{2}/16)$
contains a point from the boundary of the corresponding fundamental region. By
starting from this point and walking along the said boundary in both
directions, we will either encounter at least $\varepsilon n^{2}/16$ arcs that
are contained in $B_{\mathcal{D}}(p,\varepsilon n^{2}/4)$ (the fact that no
vertex of $G$ is contained in the boundary of a fundamental region is
important here), or go around the entirety of one of the $C_{i}^{\prime}$’s.
Hence at least one of the first two properties holds.

Suppose now that $B_{\mathcal{D}}(p,\varepsilon n^{2}/16)$ contains a heavy
edge $e$. Then, we can find at least $\varepsilon n^{2}/16$ crossing points of
$\mathcal{D}$ that involve $e$ and are contained in
$B_{\mathcal{D}}(p,\varepsilon n^{2}/8)$; apart from $e$, the edges involved
in these crossings are all distinct due to the fact that $\mathcal{D}$ is
simple. If any of these edges is light, then it must be encapsulated by
$B_{\mathcal{D}}(p,3\varepsilon n^{2}/16)$, so we can assume that at least
$\varepsilon n^{2}/32$ of them are heavy. Each of these heavy edges takes part
in at least $\varepsilon n^{2}/16$ crossing that lie in
$B_{\mathcal{D}}(p,3\varepsilon n^{2}/16)$. Summing over all of these edges
and dividing by two to account for the fact that each crossing might be
counted up to two times, we get that at least $(\varepsilon
n^{2}/32)(\varepsilon n^{2}/16)/2$ crossing points of $\mathcal{D}$ belong to
the interior of $B_{\mathcal{D}}(p,\varepsilon n^{2}/4)$.

It remains to tackle the case where the interior of
$B_{\mathcal{D}}(p,\varepsilon n^{2}/16)$ is disjoint from all the heavy
edges. Given a clean curve $C$, let $c_{1},c_{2},\dots c_{t}$ denote the
intersection points of its interior with the edges of $G$, and let $e_{i}$ be
the edge that contains $c_{i}$; we define $w_{G}(C)$ as
$\sum_{i=1}^{t}w_{G}(e_{i})$. Consider a clean curve $C_{p}$ that connects $p$
to a point on the boundary of $B_{\mathcal{D}}(p,\varepsilon n^{2}/16)$ which
is neither a crossing nor a vertex of $G$, and such that $w(C_{p})$ is minimal
amongst all curves of this kind. Furthermore, suppose that there is no curve
with the aforementioned properties which has less intersection points with the
edges than $C_{p}$ does. Each of the at least $\varepsilon n^{2}/16$ points
where the interior of $C_{p}$ intersects an edge must belong to a light edge.
Since $\mathcal{D}$ is locally optimal, no two of these points belong to the
same edge, as otherwise we would be able to construct a curve that contradicts
the choice of $C_{p}$. Hence there are at least $\varepsilon n^{2}/16$ light
edges that intersect the interior of $B_{\mathcal{D}}(p,\varepsilon n^{2}/16)$
and are thus encapsulated by $B_{\mathcal{D}}(p,\varepsilon n^{2}/4)$. ∎

The desired subdivision can now be obtained by means of a standard covering
argument. Indeed, let $P=\\{p_{1},p_{2},\dots,p_{k}\\}$ be a set of points on
the plane such that none of its elements represents a vertex or lies on an
edge or the boundary of a fundamental region, and which is maximal with the
property that $B_{\mathcal{D}}(p_{i},\varepsilon n^{2}/4)$ and
$B_{\mathcal{D}}(p_{j},\varepsilon n^{2}/4)$ are interior disjoint whenever
$i\neq j$. Given that the total complexity of the boundaries of the
fundamental regions is $O(n^{2}/\varepsilon)$, the number of
$B_{\mathcal{D}}(p_{i},\varepsilon n^{2}/4)$’s that satisfy property $1$ is
$O(1/\varepsilon^{2})$. Since the total number $C_{i}^{\prime}$’s is
$O(1/\varepsilon^{2})$, the same is true for those that satisfy property $2$.
Because the $B_{\mathcal{D}}(p_{i},\varepsilon n^{2}/4)$’s are interior
disjoint, every crossing point of $\mathcal{D}$ belongs to the interior of at
most one of them, and no edge can be encapsulated by more than one of them.
Since $\mathcal{D}$ is simple, the number of crossing points is $O(n^{4})$, so
at most $O(1/\varepsilon^{2})$ of the $B_{\mathcal{D}}(p_{i},\varepsilon
n^{2}/4)$’s contain $\varepsilon^{2}n^{4}/32^{2}$ such points or more. Lastly,
as there are no more than $O(\varepsilon^{1/2}n^{2})$ light edges, the amount
of $B_{\mathcal{D}}(p_{i},\varepsilon n^{2}/4)$’s that encapsulate at least at
$\varepsilon n^{2}/32$ light edges is upper bounded by $O(1/\varepsilon^{2})$.
This shows that $k=O(1/\varepsilon^{2})$. Now, notice that for every point $q$
we can find a $p_{i}$ such that such that
$d_{\mathcal{D}}(p_{i},q)\leq\varepsilon n^{2}/2$, or else $q$ could be added
to $P$, contradicting its maximality. For each $q$, let $P(q)\subseteq P$
denote the set of $p_{i}$’s that minimize $d_{\mathcal{D}}(p_{i},q)$, and let
$p(q)$ be the element of $p(q)$ with the smallest subscript. Define $r_{i}$ as
the closure of $\\{q\ |\ p(q)=p_{i}\\}$ for every $i\in[k]$777If $m$ is a
positive integer, then $[m]$ denotes the set $\\{1,2,\dots,m\\}$.. The
$r_{i}$’s form a subdivision of the plane, and they are closed, connected and
interior disjoint. Moreover, if $q\in r_{i}$ and $C_{q}$ is a clean curve that
connects $q$ to $r_{i}$ such that its interior has precisely
$d_{\mathcal{D}}(p_{i},p)$ intersection points with the edges of $G$, then it
is not hard to see that this curve lies completely within $r_{i}$. It follows
that any two points in $r_{i}$ can be connected by a clean curve that goes
through $p_{i}$ and whose interior crosses at most $\varepsilon n^{2}$ edges.
Lastly, the $r_{i}$’s can be modified using the process depicted in Figure 1
so as to ensure that no vertex of $G$ lies on the boundary of any of them
(this final step is where specific wording of property III comes into play).
The resulting regions satisfy properties I, II and III.

∎

As promised, we now show that there is a strong connection between
$d_{\square}$ and the crossing number.

######  Theorem 3.3.

Let $G_{1}$ and $G_{2}$ be edge weighted graphs on the same vertex set $V$ and
let $d=d_{\square}(G_{1},G_{2})$. If $d\geq n^{-4}$, then

$|\mathop{\mathrm{cr}}(G_{1})-\mathop{\mathrm{cr}}(G_{2})|\leq Md^{1/4}n^{4},$

where $M$ is an absolute constant. Meanwhile,
$|\mathop{\mathrm{cr}}(G_{1})-\mathop{\mathrm{cr}}(G_{2})|\leq d^{2}n^{8}$
holds independently of the value of $d$.

Remark: The interesting part of this result is the first inequality.

###### Proof.

The proof of Theorem 1.1 by Fox, Pach and Suk relies on a regularity lemma for
semi-algebraic graphs from*. In a sense, Theorem 3.1 will act as a purely
combinatorial substitute of the said lemma, although this analogy should not
be pushed too far.

Suppose that $d\geq n^{-4}$. By adding edges of weight $0$, we can assume that
every two elements of $V$ are adjacent in $G_{1}$. Consider a simple and
locally optimal drawing $\mathcal{D}$ of $G_{1}$ and apply Theorem 3.1 with
$\varepsilon=d^{1/8}$ to obtain a subdivision of the plane. Let
$r_{1},r_{2},\dots,r_{k}$ be the regions that contain at least one vertex and,
for each $i$, let $V_{i}\subset V$ denote the set of vertices that are
contained in $r_{i}$. We can assume that $k\leq C/\varepsilon^{2}=C/d^{1/4}$
for some absolute constant $C$. Since $\varepsilon\geq n^{-1/2}$, each of the
$V_{i}$’ has at most $\lceil\varepsilon^{2}n\rceil<2\varepsilon^{2}n$
elements. We say that an edge is long if its endpoint belong to different
$V_{i}$’s, and that it is short otherwise.

We shall use $\mathcal{D}$ as a basis for constructing a drawing
$\mathcal{D}^{\prime}$ of $G_{2}$. The elements of $V$ will be represented by
the same points as in $\mathcal{D}$. Next, for every long edge $(u,v)\in
E_{G_{2}}(V_{i},V_{j})$, choose a random edge $(u^{\prime},v^{\prime})\in
E_{G_{1}}(V_{i},V_{j})$, where $(x,y)$ is chosen with probability
$w_{G_{1}}(x,y)/e_{G_{1}}(V_{i},V_{j})$ (these selections are carried out
independently of each other for every long edge of $G_{2}$). If
$e_{G_{1}}(V_{i},V_{j})=0$, $(u^{\prime},v^{\prime})$ is chosen uniformly at
random from $E_{G_{1}}(V_{i},V_{j})$. Consider the points where the curve that
represents $(u^{\prime},v^{\prime})$ in $\mathcal{D}$ crosses the union of the
boundaries of $r_{i}$ and $r_{j}$ (if a section of the curve is contained in
the union of the boundaries, we take only its endpoints) and number them by
$p_{1},p_{2},\dots,p_{t}$ in the order that they appear as this curve is
traversed from $u$ to $v$. If some $p_{t}$ lies on the boundaries of both
$r_{i}$ and $r_{j}$, then write $a(u,v)=b(u,v)=p_{t}$. Otherwise, choose two
contiguous $p_{i}$’s $a(u,v)=p_{t}$ and $b(u,v)=p_{t\pm 1}$ such that $a(u,v)$
lies on the boundary of $r_{i}$ and $b(u,v)$ lies on the boundary of $r_{j}$.
The curve that represents $(u,v)$ will be composed of three sections: one
which goes from $u$ to $a(u,v)$, one that goes from $a(u,v)$ to $b(u,v)$ by
following along the curve that represents $(u^{\prime},v^{\prime})$ in
$\mathcal{D}$ (which is a single point in the case that $a(u,v)=b(u,v)$), and
a last one between $b(u,v)$ and $v$. The first section will be constructed so
that it is fully contained in $r_{i}$ and it has as few crossings as possible
with the edges of $G_{1}$ that have no endpoint in $V_{i}$. Analogously, we
draw the last section so that it lies in $r_{j}$ and has the least possible
number of crossings with the edges of $G_{1}$ that have no endpoint in
$V_{j}$. The first and last sections of every curve that represents a long
edge of $G_{2}$ will be called extremal. Each short edge with both endpoints
in some $V_{i}$ will be represented by a curve that is contained in $r_{i}$
and has the least possible number of crossings with the the edges of $G_{1}$
that have no endpoint in $V_{i}$. See Figure 3. Let $E_{i}$ denote the set of
curves formed by the short edges of $G_{2}$ with endpoints in $V_{i}$, and the
extremal sections with an endpoint in $V_{i}$. The above construction can be
carried out so that each element of $E_{i}$ has at most $\varepsilon n^{2}$
crossings with the edges of $G_{1}$ that have no endpoint in $V_{i}$, and such
that any two elements of $E_{i}$ have a finite number of points in common.
There might still be some pairs of elements of $E_{i}$ which cross each other
more than once, but these multiple crossings can be eliminated without
increasing the total number of crossing between the elements of $E_{i}$ and
the edges of $G_{1}$ with no endpoint in $V_{i}$. Finally, observe that some
pairs of long edges of $E_{G_{2}}(V_{i},V_{j})$ may have infinitely many
points in common if their non extremal sections coincide. Thus, in order to
obtain an actual graph drawing we might have to perturb these edges slightly
as in Figure 4. We point out that the resulting drawing is not necessarily
simple.

Figure 3: On the right, we have the curve that represents
$(u^{\prime},v^{\prime})$ in $\mathcal{D}$. Setting $a(u,v)=p_{4}$ and
$b(u,v)=p_{5}$ and proceeding as described in the proof, we arrive at a curve
that connects $u$ and $v$. Figure 4: Edges that share entire non-extremal
sections can be modified as shown above. It is important that these
modifications be carried out so that any two extremal sections cross at most
once and the number of crossings between the extremal sections in $r_{i}$ and
the edges of $G_{1}$ that do not have an endpoint in $r_{i}$ does not increase
(the same goes for $r_{j}$).

A long edge of $G_{2}$ will be called lonely if it belongs to
$E_{G_{2}}(V_{i},V_{j})$ and $e_{G_{1}}(V_{i},V_{j})\leq dn^{2}$. Note that
$G_{2}$ has no more than $dk^{2}n^{2}\leq C^{2}d^{1/2}n^{2}$ lonely edges.
Delete all the lonely edges from $\mathcal{D}^{\prime}$, we will later
describe how they can be reinserted without increasing the crossing number by
too much. A crossing point in either of $\mathcal{D}$ or
$\mathcal{D}^{\prime}$ will be called bad it there is an $V_{i}$ that contains
an endpoint of each of the two corresponding edges, and bad otherwise. There
are three types of good crossings in $\mathcal{D}^{\prime}$: the ones that
involve two non extremal sections (type $1$), those which involve a non
extremal section and the interior of an extremal one (type $2$), and those
that involve a short edge and a non extremal section (type $3$). Below, we
bound expected value of $\mathop{\mathrm{cr}}(G_{2},\mathcal{D}^{\prime})$.

Every good crossing of type $1$ in $\mathcal{D}^{\prime}$ can be traced back
to a good crossing in $\mathcal{D}$. If we think about it in this way, then a
good crossing in $\mathcal{D}$ between an edge $(u,v)\in
E_{G_{1}}(V_{i},V_{j})$ and an edge $(u^{\prime},v^{\prime})\in
E_{G_{1}}(V_{s},V_{t})$ contributes at most

$\frac{w_{G_{1}}(u,v)\cdot w_{G_{1}}(u^{\prime},v^{\prime})\cdot
e_{G_{2}}(V_{i},V_{j})\cdot
e_{G_{2}}(V_{s},V_{t})}{e_{G_{1}}(V_{i},V_{j})\cdot e_{G_{1}}(V_{s},V_{t})}$

to $\mathbf{E}[\mathop{\mathrm{cr}}(G_{2},\mathcal{D}^{\prime})]$. Let
$c_{\mathcal{D}}(i,j,s,t)$ denote the total weighted sum of the crossings
between an edge of $E_{G_{1}}(V_{i},V_{j})$ and an edge from
$E_{G_{1}}(V_{s},V_{t})$ in $\mathcal{D}$. Then, the total contribution of
these crossings to
$\mathbf{E}[\mathop{\mathrm{cr}}(G_{2},\mathcal{D}^{\prime})]$ is upper
bounded by

$c_{\mathcal{D}}(i,j,s,t)\frac{e_{G_{2}}(V_{i},V_{j})\cdot
e_{G_{2}}(V_{s},V_{t})}{e_{G_{1}}(V_{i},V_{j})\cdot
e_{G_{1}}(V_{s},V_{t})}\leq
c_{\mathcal{D}}(i,j,s,t)\frac{(e_{G_{1}}(V_{i},V_{j})+dn^{2})(e_{G_{1}}(V_{s},V_{t})+dn^{2})}{e_{G_{1}}(V_{i},V_{j})\cdot
e_{G_{1}}(V_{s},V_{t})}.$

Adding over all $4$-tuples $(i,j,s,t)$ with pairwise different entries (two
tuples are considered the same if the correspond to the same pairs of parts of
$\mathcal{P}$), we get that the expected weighted sum of the crossings of type
1 in $\mathcal{D}^{\prime}$ does not exceed

$\sum_{(i,j,s,t)}c_{\mathcal{D}}(i,j,s,t)\left(1+\frac{e_{G_{1}}(V_{i},V_{j})dn^{2}+e_{G_{1}}(V_{s},V_{t})dn^{2}+d^{2}n^{4}}{e_{G_{1}}(V_{i},V_{j})\cdot
e_{G_{1}}(V_{s},V_{t})}\right)$
$\leq\sum_{(i,j,s,t)}c_{\mathcal{D}}(i,j,s,t)+e_{G_{1}}(V_{i},V_{j})dn^{2}+e_{G_{1}}(V_{s},V_{t})dn^{2}+d^{2}n^{4}$
$\leq\mathop{\mathrm{cr}}(G_{1},\mathcal{D})+k^{4}(\varepsilon^{2}n)^{2}dn^{2}+k^{4}d^{2}n^{4}\leq\mathop{\mathrm{cr}}(G_{1},\mathcal{D})+C^{4}d^{1/2}n^{4}+C^{4}d^{2}n^{4}\leq\mathop{\mathrm{cr}}(G_{1},\mathcal{D})+2C^{4}d^{1/2}n^{4}.$

Next, we bound the amount of crossings of types $2$ and $3$ that are contained
in $r_{i}$. Note that each of them can be traced back to an intersection point
between a long edge of $G_{1}$ that has no endpoint in $V_{i}$ and a either a
short edge of $G_{2}$ with endpoints in $V_{i}$ or an extremal section with
endpoint in $V_{i}$ (i.e., an intersection point between an edge of $G_{1}$
with no endpoint in $V_{i}$ and an element of $E_{i}$). By construction, and
thanks to property $3$ in the statement of Theorem 3.1, we have that, on
average, each of the at most $\lceil\varepsilon^{2}n\rceil n$ elements of
$E_{i}$ takes part in no more than $\varepsilon n^{2}$ crossings with the long
edges of $G_{1}$ that have no endpoint in $V_{i}$. On top of this, if the long
edge of $G_{1}$ involved in one of these crossings belongs to
$E_{G_{1}}(V_{s},V_{t})$, then the crossing contributes at most

$\frac{e_{G_{2}}(V_{s},V_{t})}{e_{G_{1}}(V_{s},V_{t})}\leq\frac{e_{G_{1}}(V_{s},V_{t})+dn^{2}}{e_{G_{1}}(V_{s},V_{t})}$

to $\mathbf{E}[\mathop{\mathrm{cr}}(G_{2},\mathcal{D}^{\prime})]$. Since the
lonely edges were deleted, we may assume that $e_{G_{1}}(V_{s},V_{t})>dn^{2}$,
and thus the above quantity is less than $2$. Whence, the expected value of
the weighted sum of the crossings of types $1$ and $2$ is less than
$4\varepsilon^{3}n^{4}=4d^{3/8}n^{4}$ (recall that every edge has weight at
most $1$).

Lastly, as any two edges with an endpoint in the same $V_{i}$ induce at most
three crossings, the number of bad crossings does not surpass

$3k\binom{\lceil\varepsilon^{2}n\rceil}{2}\binom{n}{2}\leq
3k\varepsilon^{4}n^{4}\leq 3Cd^{1/4}n^{4}.$

Now we add the at most $C^{2}d^{1/2}n^{2}$ lonely edges back into the the
drawing. In order to do this, we first transform $\mathcal{D}^{\prime}$ into a
simple and locally optimal drawing by applying a sequence of operations that
does not increase the weighted sum of the crossings. Then, each lonely edge
can be represented by a curve that does not cross any non-lonely edge more
than once, and we can get rid of multiple crossings between the lonely edges
without increasing the number of crossings between lonely and non-lonely
edges. At the end, we get a drawing $\mathcal{D}^{\prime\prime}$ of $G_{2}$
that satisfies

$\mathbf{E}[\mathop{\mathrm{cr}}(G_{2},\mathcal{D}^{\prime\prime}]\leq\mathop{\mathrm{cr}}(G_{2},\mathcal{D}^{\prime})+C^{2}d^{1/2}n^{2}\binom{n}{2}\leq\mathop{\mathrm{cr}}(G_{2},\mathcal{D}^{\prime})+C^{2}d^{1/2}n^{4}$
$\leq\mathop{\mathrm{cr}}(G_{1},\mathcal{D})+2C^{4}d^{1/2}n^{4}+4d^{3/8}n^{4}+3Cd^{1/4}n^{4}+C^{2}d^{1/2}n^{4}$
$\leq\mathop{\mathrm{cr}}(G_{1},\mathcal{D})+Md^{1/4}n^{4},$

where $M$ is an absolute constant. As this can be repeated for every drawing
$\mathcal{D}$ of $G_{1}$, we arrive at
$\mathop{\mathrm{cr}}(G_{2})\leq\mathop{\mathrm{cr}}(G_{1})+Md^{1/4}n^{4}$.
Analogously,
$\mathop{\mathrm{cr}}(G_{2})\leq\mathop{\mathrm{cr}}(G_{1})+Md^{1/4}n^{4}$.
This proves the first part of the statement. For the second part, a direct
computation yields
$\mathop{\mathrm{cr}}(G_{2},\mathcal{D})\leq\mathop{\mathrm{cr}}(G_{1},\mathcal{D})+d^{2}n^{8}$,
and we can finish as above. ∎

######  Theorem 3.4.

For any edge weighted graph $G=(V,E)$ and any positive integer $m$, we have
that

$0\leq\mathop{\mathrm{cr}}(G[m])-m^{4}\mathop{\mathrm{cr}}(G)\leq n^{3}m^{4}.$

###### Proof.

This was shown to be true for the rectilinear crossing number (instead of the
crossing number) in [18], the proof of this version is almost identical to the
one that appears in the said paper.

We begin by proving the inequality on the left. Consider a simple drawing
$\mathcal{D}$ of $G[m]$ which attains $\mathop{\mathrm{cr}}(G)$. From this
drawing, we obtain a drawing $\mathcal{D}^{\prime}$ of $G$ in the following
way: For each $v\in V$, choose uniformly at random an element $v^{\prime}$
from $U_{v}$ (see the definition of $G[m]$ in subsection 2.2); the point
$p_{v}$ that represents $v^{\prime}$ in $\mathcal{D}$ will also be used to
represent $v$ in $\mathcal{D}^{\prime}$. Once all these points have been
chosen, notice that for every pair of adjacent vertices $u$ and $v$ of $G$ the
points $p_{v}$ and $p_{u}$ are connected by a curve in $\mathcal{D}$; this is
the curve that will represent the edge $(u,v)$ in $\mathcal{D}^{\prime}$.
Clearly, $\mathcal{D}^{\prime}$ is simple. For any two non-adjacent edges
$e_{1}=(a,b),e_{2}=(c,d)\in E$, the probability that they cross in
$\mathcal{D}^{\prime}$ is $c(U_{a},U_{b},U_{c},U_{d})/m^{4}$, where
$c(U_{a},U_{b},U_{c},U_{d})$ denotes the number of quadruples
$(a^{\prime},b^{\prime},c^{\prime},d^{\prime})$ with $a^{\prime}\in U_{a}$,
$b^{\prime}\in U_{b}$, $c^{\prime}\in U_{c}$, $d^{\prime}\in U_{d}$ such that
the edges $(a^{\prime},b^{\prime})$ and $(c^{\prime},d^{\prime})$ cross each
other in $\mathcal{D}$. From this, we get that

$\mathbf{E}[\mathop{\mathrm{cr}}(G,\mathcal{D}^{\prime})]\leq\mathop{\mathrm{cr}}(G[m],\mathcal{D})/m^{4}=\mathop{\mathrm{cr}}(G[m])/m^{4}.$

Since
$\mathop{\mathrm{cr}}(G)\leq\mathbf{E}[\mathop{\mathrm{cr}}(G,\mathcal{D}^{\prime})]$,
the result follows.

Now we prove the inequality on the right. Take a drawing $\mathcal{D}$ of $G$
that attains $\mathop{\mathrm{cr}}(G)$ and let $\varepsilon$ be a very small
positive real (this will be made more precise in a moment). We obtain a
drawing $\mathcal{D}^{\prime}$ of $G[m]$ as follows: For every $v\in V$,
replace the point that represents $v$ by a set of $m$ distinct points, each of
them at distance at most $\varepsilon$ from the original one; these points
will represent the elements of $U_{v}$. For each $(u,v)\in E$, we draw all the
edges between $U_{u}$ and $U_{v}$ by following along the curve that represents
$(u,v)$ in $\mathcal{D}$ (this makes sense if $\varepsilon$ is small enough),
making sure that no two edges of $G_{[}m]$ cross each other more than once. We
call a $4$-tuple $(a,b,c,d)$ of vertices of $G[m]$ bad if two of its elements
belong to the same $U_{v}$, and good otherwise. If $\varepsilon$ is small
enough, then for any good $4$-tuple $(a,b,c,d)$ with $a\in U_{a}^{\prime}$,
$b\in U_{b}^{\prime}$, $c\in U_{c}^{\prime}$, $d\in U_{d}^{\prime}$ the edges
$(a,b)$ and $(c,d)$ cross in $\mathcal{D}^{\prime}$ if and only if $(a,b)$ and
$(c,d)$ cross in $\mathcal{D}$. On the other hand, the number of bad
$4$-tuples is less than $n\binom{m}{2}\binom{nm}{2}$, so we have at

$\mathop{\mathrm{cr}}(G[m])\leq\mathop{\mathrm{cr}}(G[m],\mathcal{D}^{\prime})\leq
m^{4}\mathop{\mathrm{cr}}(G,\mathcal{D})+n\binom{m}{2}\binom{nm}{2}\leq
m^{4}\mathop{\mathrm{cr}}(G)+n^{3}m^{4}.$

∎

By theorems 3.3 and 3.4, the crossing density of graphs satisfies properties
(i) and (ii) in subsection 2.3, and it definitely satisfies (iii) as well.
This implies that the crossing density is an estimable graph parameter. That
the rectilinear crossing density is estimable was already clear to the authors
of [18].

######  Theorem 3.5.

The crossing and rectilinear crossing densities are estimable graph
parameters. As a consequence, there exist two functionals $g$ and
$\overline{g}$ on $W_{0}$ such that
$\lim_{n\rightarrow\infty}\mathop{\mathrm{cd}}(G_{n})=g(W)$ and
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(G_{n})=\overline{g}(W)$
whenever $G_{1},G_{2},\dots$ converges to $W$ and the number of vertices of
$G_{n}$ goes to infinity with $n$.

### The algorithm

Here, we present the proof of Theorem 1.2. The algorithm we are about to
describe is very similar to the one in [18] (see Theorem 1.1).

  1. 1.

We are given an $n$-vertex graph $G=(V,E)$ as input.

  2. 2.

Set $\varepsilon=(\log\log n)^{-\frac{1}{2c}}$ and use Theorem 2.2 to find an
equitable Frieze-Kannan $\varepsilon$-regular partition
$\mathcal{P}=\\{V_{1},V_{2},\dots,V_{k}\\}$ of $G$, where $k\leq
O(2^{\sqrt{\log\log n}})$ (here, $c$ denotes the constant in the satement of
the said theorem). This takes $n^{2+o(1)}$ time.

  3. 3.

Consider the edge weighted graph $G/\mathcal{P}$ and compute its crossing
number using Theorem 2.1. Then, output $cr(G/\mathcal{P})(n/k)^{4}$. This can
be done in $2^{O(k^{4}\log k)}=n^{o(1)}$ time.

###### Proof of Correctness.

By Theorem 3.4, the blow-up $(G/\mathcal{P})[\lfloor n/K\rfloor]$ has crossing
number at most $\text{cr}(G/\mathcal{P})(n/k)^{4}$. The graph
$(G/\mathcal{P})[\lfloor n/K\rfloor]$ can be obtained from $G_{\mathcal{P}}$
by removing less than $k$ vertices (along with the attached edges), thus
$\text{cr}(G_{\mathcal{P}})\leq(G/\mathcal{P})[\lfloor n/K\rfloor]+kn^{3}$.
Finally, $\mathcal{P}$ was chosen so that
$|G-G_{\mathcal{P}}|\leq\varepsilon$, so Theorem 3.3 yields
$|\text{cr}(G)-\text{cr}(G_{\mathcal{P}})|\leq M\varepsilon^{1/4}n^{4}$. These
observations imply that

$\text{cr}(G)\leq\text{cr}(G/\mathcal{P})(n/k)^{4}+kn^{3}+M\varepsilon^{1/4}n^{4}\leq\text{cr}(G/\mathcal{P})(n/k)^{4}+O\left(\frac{n^{4}}{(\log\log
n)^{\frac{1}{8c}}}\right).$

∎

  4. 4.

If we also wish to find a drawing of $G$ with
$\mathop{\mathrm{cr}}(G)+O(n^{4}/(\log\log n)^{\delta^{\prime}})$ crossings,
then we first need access to a simple and locally optimal drawing of drawing
of $G_{\mathcal{P}}$ (or a graph that is very close to $G_{\mathcal{P}}$ with
respect to $d_{\square}$) with crossing number
$\mathop{\mathrm{cr}}(G_{\mathcal{P}})+O(n^{4}/(\log\log
n)^{\delta^{\prime}})$. A drawing of $G_{\mathcal{P}}$ with this many
crossings can be obtained by combining the drawing of $G/\mathcal{P}$ provided
by 2.1 with the technique used in the proof of the right side inequality in
the statement of Theorem 3.4 (see the above proof). Now, we round the weights
of the edges so that they can be written as an integer divided by
$O(1/(\log\log n)^{\delta^{\prime}/2})$, thus obtaining a new graph
$G_{\mathcal{P}}^{\prime}$ whose crossing number differs from that of
$G_{\mathcal{P}}$ by at most $O(n^{4}/(\log\log n)^{\delta^{\prime}})$. In
order to construct a locally optimal drawing of $G_{\mathcal{P}}^{\prime}$, we
iteratively refine the drawing by using Dijkstra’s algorithm to redraw the
edges until it is no longer possible to keep going. Each step reduces the
weighted sum of the crossings by $\Omega(1/(\log\log n)^{\delta^{\prime}})$,
so the whole process takes polynomial-time. Now we can follow the proof of
Theorem 3.3, which is essentially algorithmic, to obtain a drawing of $G$. At
some point during this procedure, we also require a locally optimal drawing of
a certain subgraph of $G$; this drawing can be constructed just as we did for
$G_{\mathcal{P}}^{\prime}$, since every step reduces the weighted sum of the
crossings by at least $1$. The expected number of crossings in the resulting
drawing of $G$ is $\mathop{\mathrm{cr}}(G)+o(n^{4})$, and the probability that
the algorithm fails to deliver a drawing with crossing number close to this
quantity can be bounded from above using the fact that the no drawing with
crossing number less than $\mathop{\mathrm{cr}}(G)$ can ever be generated.

Remark: The only step of the above algorithm at which we produce an actual
graph drawing is at the end. Before that, drawings are processed not as
geometric objects, but combinatorial ones (in the sense that they are stored
as planar maps with a vertex for each crossing point and for each vertex of
the original graph). The final drawing can be constructed using any efficient
algorithm for drawing planar graphs (see Chapter 6 in [41] for many such
algorithms).

##  4 Crossing densities of graphons

We will first introduce the rectilinear crossing density of a graphon, but
before that, we need some preliminaries. For any four (not necessarily
distinct) points $x,y,z,w\in\mathbb{R}^{2}$, let $I(x,y,z,w)=1$ if
$\text{conv}\\{x,y\\}\cap\text{conv}\\{z,w\\}\neq\emptyset$ and $I(x,y,z,w)=0$
otherwise. We claim that $I$, as a function from $(\mathbb{R}^{2})^{4}$ to
$\mathbb{R}$, is measurable. Indeed, let

$X=\\{(x,y,z,w)\in(\mathbb{R}^{2})^{4}:\ |\\{x,y,z,w\\}|\leq 3\ \text{or}\
x,y,z,w\ \text{are contained in a single line}\\}.$

The restriction of $I$ to $X$ can easily be seen to be measurable. Hence, it
suffices to show that $I^{-1}(1)\backslash X\subset(\mathbb{R}^{2})^{4}$ is
measurable. For every positive integer $m$, consider a grid-like subdivision
of the plane into interior disjoint squares of side length $1/m$, which we
denote by $S_{m,1},S_{m,2},\dots$ in any order. Let
$A_{m}\subset\mathbb{N}^{4}$ be the set of all $4$-tuples $(a,b,c,d)$ such
that $I(x,y,z,w)=1$ whenever $x\in S_{m,a},\ y\in S_{m,b},\ z\in S_{m,c},\
w\in S_{m,d}$. Write

$B_{m}=\bigcup_{(a,b,c,d)\in A_{m}}S_{m,a}\times S_{m,b}\times S_{m,c}\times
S_{m,d}.$

By definition, $I(B_{m})=1$, and it is not hard to see that the measurable set
$B=\cup_{i=1}^{\infty}B_{i}$ covers $I^{-1}(1)\backslash X$. Thus,
$I^{-1}(1)\backslash X=B\backslash X$, which implies the claim.

As a consequence of the above result, if $f:[0,1]\rightarrow\mathbb{R}^{2}$ is
measurable then the function $I_{f}:[0,1]^{4}\rightarrow[0,1]$ defined by
$I_{f}(x,y,z,w)=I(f(x),f(y),f(z),f(w))$ is measurable too. Denote the family
of all bounded measurable functions from $[0,1]$ to $\mathbb{R}^{2}$ by
$\mathcal{F}$. Given a graphon $W$ and a function $f\in\mathcal{F}$, let

$\overline{\mathop{\mathrm{cd}}}(W,f)=\frac{1}{8}\int_{[0,1]^{4}}W(x_{1},x_{2})W(x_{3},x_{4})I_{f}(x_{1},x_{2},x_{3},x_{4})\prod_{i=1}^{4}dx_{i}.$

By the discussion above, this integral is well defined. The function $f$ can
be thought of as a straight-line drawing of $W$; in fact, the definition of
$\overline{\mathop{\mathrm{cd}}}(W,f)$ is essentially the continuous (and
normalized) analog of the definition of
$\overline{\mathop{\mathrm{cr}}}(G,\mathcal{D})$ given in Section 2. We divide
by $8$ to make up for the fact the each crossing is counted eight times by the
integral. The rectilinear crossing density of $W$ is defined as

$\overline{\mathop{\mathrm{cd}}}(W)=\inf_{f\in\mathcal{F}}\overline{\mathop{\mathrm{cd}}}(W,f).$

The definition of the crossing density of a graphon is somewhat more
intricate. Let $\mathcal{C}$ denote the family of all curves
$c:[0,1]\rightarrow\mathbb{R}^{2}$ that are either simple or constant888Up to
this point, we had used the term curve to refer to the image of a continuous
function from an interval to the plane. From here on, both the function and
its image will be referred to as curves. A simple graphon drawing is a
function $\mathcal{D}:[0,1]^{2}\rightarrow\mathcal{C}$ such that the following
properties hold:

  1. 1.

For any $x,y,t\in[0,1]$, $\mathcal{D}(x,y)(t)=\mathcal{D}(y,x)(1-t)$.

  2. 2.

For every $x\in[0,1]$, the image of $\mathcal{D}(x,x)$ is a single point,
which we denote by $\mathcal{D}(x)$.

  3. 3.

For any $x,y\in[0,1]$, $\mathcal{D}(x,y)(0)=\mathcal{D}(x)$.

  4. 4.

For any $x_{1},x_{2},y_{1},y_{2}\in[0,1]$, if the images of
$\mathcal{D}(x_{1},y_{1})$ and $\mathcal{D}(x_{2},y_{2})$ are not equal (as
subsets of $\mathbb{R}^{2}$), then they have at most one point in common.

For a graphon drawing $\mathcal{D}$ and $x,y,z,w\in[0,1]$, let
$I_{\mathcal{D}}(x,y,z,w)=1$ if the curves $\mathcal{D}(x,y)$ and
$\mathcal{D}(z,w)$ have at least one point in common, and
$I_{\mathcal{D}}(x,y,z,w)=0$ otherwise. Let $\mathcal{D}_{\mathcal{W}}$ denote
the family of all simple graphon drawings $\mathcal{D}$ such that
$I_{\mathcal{D}}$ is measurable. Given a graphon $W$ and a graphon drawing
$\mathcal{D}\in\mathcal{D}_{\mathcal{W}}$, write

$\mathop{\mathrm{cd}}(W,\mathcal{D})=\frac{1}{8}\int_{[0,1]^{4}}W(x_{1},x_{2})W(x_{3},x_{4})I_{\mathcal{D}}(x_{1},x_{2},x_{3},x_{4})\prod_{i=1}^{4}dx_{i}.$

The crossing density of $W$ is defined as

$\mathop{\mathrm{cd}}(W)=\inf_{\mathcal{D}\in\mathcal{D}_{\mathcal{W}}}\mathop{\mathrm{cd}}(W,\mathcal{D}).$

Remark: We feel the need to clarify that, even though we make a slight abuse
of notation by using each of $\mathop{\mathrm{cd}}$ and
$\overline{\mathop{\mathrm{cd}}}$ to denote both a graph parameter and a
functional on $\mathcal{W}_{0}$, it is not necessarily true that
$\mathop{\mathrm{cd}}(G)=\mathop{\mathrm{cd}}(W_{G})$ or
$\overline{\mathop{\mathrm{cd}}}(G)=\overline{\mathop{\mathrm{cd}}}(W_{G})$
(see Theorem 4.3 below). Also, it is not completely evident from the
definitions that
$\overline{\mathop{\mathrm{cd}}}(W)\leq\mathop{\mathrm{cd}}(W)$, but this
inequality does hold for every $W\in\mathcal{W}_{0}$.

At this point, it is natural to ask whether for every graphon $W$ there is an
$f\in\mathcal{F}$ such that
$\overline{\mathop{\mathrm{cr}}}(W)=\overline{\mathop{\mathrm{cr}}}(W,f)$, or
a $\mathcal{D}\in\mathcal{D}_{\mathcal{W}}$ such that
$\mathop{\mathrm{cd}}(W)=\mathop{\mathrm{cd}}(W,\mathcal{D})$ (in other words,
can the infimum be substituted by a minimum in the above definitions?).
Unfortunately, we do not know the answer to either of these question. The
following result, however, is an immediate consequence of the Banach-Alaoglu
theorem.

######  Lemma 4.1.

There exist two families $\overline{\mathcal{I}}$ and $\mathcal{I}$ of
measurable functions from $\mathbb{R}^{4}$ to $\mathbb{R}$ such that, for
every $W\in\mathcal{W}_{0}$, we have

$\overline{\mathop{\mathrm{cd}}}(W)=\min_{I\in\overline{\mathcal{I}}}\frac{1}{8}\int_{[0,1]^{4}}W(x_{1},x_{2})W(x_{3},x_{4})I(x_{1},x_{2},x_{2},x_{4})\prod_{i=1}^{4}dx_{i}$

and

$\mathop{\mathrm{cd}}(W)=\min_{I\in\mathcal{I}}\frac{1}{8}\int_{[0,1]^{4}}W(x_{1},x_{2})W(x_{3},x_{4})I(x_{1},x_{2},x_{2},x_{4})\prod_{i=1}^{4}dx_{i}.$

Furthermore, these families can be chosen so that all of their elements take
values in $[0,1]$.

###### Proof.

Consider the sets $A=\\{I_{f}\ |\ f\in\mathcal{F}\\}$ and
$B=\\{I_{\mathcal{D}}\ |\ \mathcal{D}\in\mathcal{D}_{\mathcal{W}}\\}$. By
Banach-Alaoglu, any sequence of elements of $A$ has a subsequence that is
convergent in the weak* topology999A sequence $f_{1},f_{2},\dots$ of
integrable functions defined on $[0,1]^{4}$ is weak* convergent if for any
integrable function $g$ defined on the same set we have that $\langle
f_{n},g\rangle=\int_{[0,1]^{4}}f_{n}g\text{ }dx$ converges as $n$ goes to
infinity., and the same is true for $B$. Now, let $W\in\mathcal{W}_{0}$ and
take a sequence $f_{1},f_{2},\dots$ of elements of $\mathcal{F}$ such that
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cr}}}(W,f_{n})=\overline{\mathop{\mathrm{cr}}}(W)$.
We can pass to a subsequence $f^{\prime}_{1},f^{\prime}_{2},\dots$ such that
$I_{f^{\prime}_{1}},I_{f^{\prime}_{2}},\dots$ converges in the weak* topology
to a measurable function $I$, which can clearly be chosen so that it takes
values in $[0,1]$. $I$ satisfies

$\overline{\mathop{\mathrm{cd}}}(W)=\frac{1}{8}\int_{[0,1]^{4}}W(x_{1},x_{2})W(x_{3},x_{4})I(x_{1},x_{2},x_{2},x_{4})\prod_{i=1}^{4}dx_{i}.$

Hence, setting $\overline{\mathcal{I}}$ to be the set formed by all elements
of $A$ and all sequential limit points of $A$ with respect to the weak*
topology does the job. In the same way, we can show that the set $\mathcal{I}$
which consists of all elements of $B$ and all of its sequential limit points
has the required properties. ∎

For every $W\in\mathcal{W}_{0}$, let
$\overline{I}_{W}\in\overline{\mathcal{I}}$ and $I_{W}\in\mathcal{I}$ denote
two functions that attain the minimums in the statement of Lemma 4.1. The
questions above can now be restated as follows. Given a graphon $W$, can the
functions $\overline{I}_{W}$ and $I_{W}$ be chosen so that
$\overline{I}_{W}=I_{f}$ for some $f\in\mathcal{F}$ and
$I_{W}=I_{\mathcal{D}}$ for some $\mathcal{D}\in\mathcal{D}_{\mathcal{W}}$?

One of the main goals of this section is to show that the crossing and
rectilinear crossing densities are continuous with respect to $d_{\square}$
(see Theorem 4.4). In order to accomplish this, we first require a weaker
version of this result.

######  Theorem 4.2.

If $W_{1},W_{2},\dots$ is a sequence of graphons that converges to another
graphon $W$ almost everywhere, then

$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})=\overline{\mathop{\mathrm{cd}}}(W),\
\lim_{n\rightarrow\infty}\mathop{\mathrm{cd}}(W_{n})=\mathop{\mathrm{cd}}(W).$

###### Proof.

The tensor product of any two graphons $W_{1}$ and $W_{2}$ is the function
$W_{1}\otimes W_{2}:[0,1]^{4}\rightarrow[0,1]$ defined by $(W_{1}\otimes
W_{2})(x,y,z,w)=W_{1}(x,y)W_{2}(z,w)$.

Consider a sequence of graphons $W_{1},W_{2},\dots$ that converges to
$W\in\mathcal{W}_{0}$ almost everywhere. Clearly, the sequence $W_{1}\otimes
W_{1},W_{2}\otimes W_{2},\dots$ converges to $W\otimes W$ almost everywhere.
Choose a subsequence $W_{1}^{\prime},W_{2}^{\prime},\dots$ of
$W_{1},W_{2},\dots$ with
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n}^{\prime})=\liminf_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})$
and, for every $n$, let $f_{n}$ be an element of $\mathcal{F}$ such that
$\overline{\mathop{\mathrm{cd}}}(W_{n},f_{n})\leq\overline{\mathop{\mathrm{cd}}}(W)+1/2^{n}$.
By Banach-Alaoglu, we can pass to a subsequence
$W_{s(1)}^{\prime},W_{s(2)}^{\prime},\dots$ of
$W_{1}^{\prime},W_{2}^{\prime},\dots$ such that
$\overline{I}_{f_{s(1)}},\overline{I}_{f_{s(2)}},\dots$ converges to some
$I\in\overline{\mathcal{I}}$ in the weak* topology. This way,

$\overline{\mathop{\mathrm{cd}}}(W_{s(n)}^{\prime})\leq\frac{1}{8}\int_{[0,1]^{4}}(W_{s(n)}^{\prime}\otimes
W_{s(n)}^{\prime})\overline{I}_{f_{s(n)}}(x_{1},x_{2},x_{3},x_{4})\prod_{i=1}^{4}dx_{i}\leq\overline{\mathop{\mathrm{cd}}}(W_{s(n)}^{\prime})+1/2^{s(n)}$

for every positive integer $n$, and so the expression on the middle converges
to

$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{s(n)}^{\prime})=\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n}^{\prime})=\liminf_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})$

as $n$ goes to infinity. On the other hand, now a standard analysis argument
shows that the sequence $(W_{s(1)}\otimes
W_{s(1)})\cdot\overline{I}_{f_{s(1)}},(W_{s(1)}\otimes
W_{s(1)})\cdot\overline{I}_{f_{s(1)}},\dots$ converges to $(W\otimes W)\cdot
I$ in the weak* topology. Putting everything together, we get that

$\liminf_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})=\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{s(n)}^{\prime})=\overline{\mathop{\mathrm{cd}}}(W,I)\geq\overline{\mathop{\mathrm{cd}}}(W).$

Now, observe that

$\overline{\mathop{\mathrm{cd}}}(W_{n})\leq\overline{\mathop{\mathrm{cd}}}(W_{n},\overline{I}_{W})=\frac{1}{8}\int_{[0,1]^{4}}(W_{n}\otimes
W_{n})\overline{I}_{W}(x_{1},x_{2},x_{3},x_{4})\prod_{i=1}^{4}dx_{i}$

for every $n$. Since the expression on the right converges to
$\overline{\mathop{\mathrm{cd}}}(W,I_{W})=\overline{\mathop{\mathrm{cd}}}(W)$
as $n$ goes to infinity, we arrive at
$\limsup_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})\leq\overline{\mathop{\mathrm{cd}}}(W)$,
but we also had
$\liminf_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})\geq\overline{\mathop{\mathrm{cd}}}(W)$;
this can only occur if
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})=\overline{\mathop{\mathrm{cd}}}(W)$.
The proof of
$\lim_{n\rightarrow\infty}\mathop{\mathrm{cd}}(W_{n})=\mathop{\mathrm{cd}}(W)$
is analogous. ∎

Next, we establish a formal connection between the crossing densities of
graphons and the crossing densities of graphs.

######  Theorem 4.3.

For every edge weighted graph $G$ on $n$ vertices, we have that

$0\leq\overline{\mathop{\mathrm{cd}}}(W_{G})-\overline{\mathop{\mathrm{cd}}}(G)\leq
1/n,\ 0\leq\mathop{\mathrm{cd}}(W_{G})-\mathop{\mathrm{cd}}(G)\leq 1/n.$

###### Proof.

Let $v_{1},v_{2},\dots,v_{n}$ denote the vertices of $G$ and
$I_{1},I_{2},\dots,I_{n}$ be the corresponding subintervals of $[0,1]$ (see
the definition of $W_{G}$ in subsection 2.2). The argument is similar to the
one in the proof of Theorem 3.4. We begin by showing the inequalities about
rectilinear crossing densities.

Given any $f\in\mathcal{F}$, we get a drawing $\mathcal{D}_{f}$ of $G$ as
follows: For every $v_{i}$, choose uniformly at random an element $x_{i}$ from
$I_{i}$; the point $f(x_{i})$ will represent $v_{i}$. Draw every edge of $G$
as a segment joining its endpoints and, if necessary, perturb the vertices
slightly so that no three of them lie on a line and no three edges have a
common interior point. Note that the vertex perturbation step can be carried
out without increasing the crossing number. A straightforward computation
shows that

$\mathbf{E}[\overline{\mathop{\mathrm{cd}}}(G,\mathcal{D}_{f})]\leq\overline{\mathop{\mathrm{cd}}}(W_{G},f).$

Since this holds for every $f\in\mathcal{F}$, we get that
$\overline{\mathop{\mathrm{cd}}}(G)\leq\overline{\mathop{\mathrm{cd}}}(W_{G})$.

Suppose now that we are given a rectilinear drawing $\mathcal{D}$ of $G$. This
drawing induces an $f_{\mathcal{D}}\in\mathcal{F}$, which is defined by
$f_{\mathcal{D}}(x)=p_{i}$, where $i$ is such that $x\in I_{i}$ and $p_{i}$ is
the point that represents $v_{i}$ in $\mathcal{D}$. The value of
$\overline{\mathop{\mathrm{cd}}}(f_{\mathcal{D}},W_{G})$ is upper bounded by
$\overline{\mathop{\mathrm{cd}}}(G)+1/n$, where the $1/n$ accounts for the the
$4$-tuples of points in $[0,1]$ which contain two elements of some interval
$S_{i}$ (these $4$-tuples are similar to the bad $4$-tuples in the proof of
Theorem 3.4). This yields
$\overline{\mathop{\mathrm{cd}}}(W_{G})\leq\overline{\mathop{\mathrm{cd}}}(G)+1/n$.

The proof of the second part of the statement proceeds in essentially the same
way. Let $\mathcal{D}\in\mathcal{D}_{\mathcal{W}}$ and construct a drawing
$\mathcal{D}^{\prime}$ of $G$ by placing $v_{i}$ at $\mathcal{D}(x)$, where
$x$ is chosen uniformly at random from $I_{i}$, and then using the curve
$\mathcal{D}(x_{i},x_{j})$ to represent the edge $(v_{i},v_{j})$. Again, we
might have to tweak the drawing slightly so that no edges goes through a
vertex, no two edges are tangent, and no three edges cross each other at the
same point. As above, we have that

$\mathbf{E}[\mathop{\mathrm{cd}}(G,\mathcal{D}^{\prime})]\leq\mathop{\mathrm{cd}}(W_{G},\mathcal{D}),$

which implies $\mathop{\mathrm{cd}}(G)\leq\mathop{\mathrm{cd}}(W_{G})$.

Finally, for every drawing $\mathcal{D}$ of $G$ we obtain an element
$\mathcal{D}^{\prime}$ of $\mathcal{D}_{\mathcal{W}}$ in the following way:
For every $x,y\in[0,1]$ with $x\in I_{i},y\in I_{j}$, set
$\mathcal{D}^{\prime}(x,y)$ to be the curve that represents the edge
$(v_{i},v_{j})$ whenever $i\neq j$, and set it to be a constant otherwise
(this constant is precisely the point that represents $v_{i}$ in
$\mathcal{D}$). As with the rectilinear crossing densities, this graphon
drawing satisfies
$\mathop{\mathrm{cd}}(W_{G},\mathcal{D}^{\prime})\leq\mathop{\mathrm{cd}}(G)+1/n$,
and the result follows. ∎

Theorems 3.5 and 4.3 can now be combined to obtain the following key result.

######  Theorem 4.4.

The crossing density and the rectilinear crossing density are continuous with
respect to the cut norm $d_{\square}$. Furthermore, if $G_{1},G_{2},\dots$ is
a convergent sequence of edge weighted graphs and the number of vertices of
$G_{n}$ goes to infinity with $n$, then
$\lim_{n\rightarrow\infty}\mathop{\mathrm{cd}}(G_{i})$ exists and is equal to
$\mathop{\mathrm{cd}}(W)$. The same is true with
$\overline{\mathop{\mathrm{cd}}}$ in place of $\mathop{\mathrm{cd}}$.

###### Proof.

Let $W\in\mathcal{W}_{0}$. We shall exhibit a sequence of graphs
$G_{1},G_{2},\dots$ such that $W_{G_{1}},W_{G_{2}},\dots$ converges to $W$ and
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})=\overline{\mathop{\mathrm{cd}}}(W),\
\lim_{n\rightarrow\infty}\mathop{\mathrm{cd}}(W_{n})=\mathop{\mathrm{cd}}(W)$.
Suppose for a moment that such a sequence exists. Then, it must be the case
that $\overline{\mathop{\mathrm{cd}}}$ and the functional $\overline{g}$
mentioned in Theorem 3.5 are one and the same, and this also true for
$\mathop{\mathrm{cd}}$ and $g$. Since $\overline{g}$ and $g$ are continuous
with respect to $d_{\square}$, so too are $\overline{\mathop{\mathrm{cd}}}$
and $\mathop{\mathrm{cd}}$. In order to construct this graph sequence, we need
some preliminaries.

For any $W\in\mathcal{W}$ and any partition
$\mathcal{P}=\\{S_{1},S_{2},\dots,S_{n}\\}$ of the unit interval into
measurable sets, let $W_{\mathcal{P}}^{\text{diag}}$ be the graphon such that
$W_{\mathcal{P}}^{\text{diag}}(x,y)=W_{\mathcal{P}}(x,y)$ if $x$ and $y$ lie
in different parts of $\mathcal{P}$, and
$W_{\mathcal{P}}^{\text{diag}}(x,y)=0$ otherwise. The advantage that we gain
from using $W_{\mathcal{P}}^{\text{diag}}$ instead of $W_{\mathcal{P}}$ is
that if $\mathcal{P}$ is a partition of $[0,1]$ into intervals of the same
length, then $W_{\mathcal{P}}^{\text{diag}}=W_{G}$ for some graph $G$. Note
that, if we let $\mathcal{P}_{n}$ be the partition into intervals of length
$1/n$ for every positive integer $n$, then each pair of distinct points in
$[0,1]$ is separated by all but a finite amount of the $P_{i}$’s. As a
consequence, the sequence $W_{\mathcal{P}_{1}},W_{\mathcal{P}_{2}},\dots$
converges to $W$ almost everywhere. Observe that for every point
$(x,y)\in[0,1]^{2}$ with $x\neq y$ there exists an integer $N$ such that
$W_{\mathcal{P}_{n}}(x,y)=W_{\mathcal{P}_{n}}^{\text{diag}}(x,y)$ whenever
$n\geq N$. This implies that the sequence
$W_{\mathcal{P}_{1}}^{\text{diag}},W_{\mathcal{P}_{2}}^{\text{diag}},\dots$
converges to $W$ almost everywhere too. Let $G_{1},G_{2},\dots$ be edge
weighted graphs such that $W_{G_{n}}=W_{\mathcal{P}_{n}}^{\text{diag}}$ for
every $n$, then, $W_{G_{1}},W_{G_{2}},\dots$ converges to $W$ almost
everywhere and Theorem 4.2 implies that
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})=\overline{\mathop{\mathrm{cd}}}(W)$
and
$\lim_{n\rightarrow\infty}\mathop{\mathrm{cd}}(W_{n})=\mathop{\mathrm{cd}}(W)$.
Since convergence almost everywhere implies convergence with respect to
$d_{\square}$, the result follows. ∎

A graphon parameter $g$ is said to be invariant if $g(W_{1})=g(W_{2})$
whenever $W_{1}$ and $W_{2}$ are weakly isomorphic. As an immediate
consequence of the above theorem, we get that
$\overline{\mathop{\mathrm{cd}}}$ and $\mathop{\mathrm{cd}}$ are invariant.

######  Corollary 4.5.

The crossing density and the rectilinear crossing density of graphons are
invariant parameters.

We point out that this can also be deduced in a more natural way without
having to recur, indirectly, to crossing densities of graphs.

Let $W^{p}$ denote the constant graphon defined by $W^{p}(x,y)=p$ for all
$x,y\in[0,1]$. Theorem 4.4 also has the following corollary, which ties
together the crossing densities with some of the problems we briefly mentioned
during the introduction.

######  Corollary 4.6.

We have that

$\lim_{n\rightarrow\infty}\frac{\overline{\mathop{\mathrm{cr}}}(K_{n})}{\binom{n}{4}}=24\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(K_{n})=24\overline{\mathop{\mathrm{cd}}}(W^{1})$

and, similarly

$\lim_{n\rightarrow\infty}\frac{\mathop{\mathrm{cr}}(K_{n})}{\binom{n}{4}}=24\mathop{\mathrm{cd}}(W^{1}).$

Clearly, if $c\geq 0$ and $W_{1}$ and $W_{2}$ are graphons with
$W_{1}=cW_{2}$, then
$\mathop{\mathrm{cd}}(W_{1})=c^{2}\cdot\mathop{\mathrm{cd}}(W_{2})$ and
$\overline{\mathop{\mathrm{cd}}}(W_{1})=c^{2}\cdot\overline{\mathop{\mathrm{cd}}}(W_{2})$.
Crossing numbers of random graphs have received considerable attention (see,
for example, [39]). A sequence $G_{1},G_{2},\dots$ of edge weighted graphs is
said to be quasi-random with density $p$ if the orders of the graphs go to
infinity with $n$ and $W_{G_{1}},W_{G_{2}},\dots$ converges to $W^{p}$. There
are many other equivalent (and often more practical) definitions of quasi-
randomness (see [11, 29]), but we restrict ourselves to this one because it is
the most convenient for us. The results in [18] directly imply that the
rectilinear crossing densities of any quasi-random sequence of graphs
converge. We can show that the same is true for the crossing density; in fact,
if we write $\overline{K}=\overline{\mathop{\mathrm{cd}}}(W_{1})$ and
$K=\mathop{\mathrm{cd}}(W_{1})$, then $\mathop{\mathrm{cd}}(W^{p})=Kp^{2}$ and
$\overline{\mathop{\mathrm{cd}}}(W^{p})=\overline{K}p^{2}$, whence Theorem 4.4
yields the following.

######  Corollary 4.7.

Let $p\in[0,1]$. Then, for any sequence $G_{1},G_{2},\dots$ of edge weighted
graphs that is quasi-random with density $p$, we have that
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(G_{n})=\overline{K}p^{2}$
and $\lim_{n\rightarrow\infty}\mathop{\mathrm{cd}}(G_{n})=Kp^{2}$.

Below, we obtain some additional properties of the crossing densities. The
next observation is a direct consequence of the definitions of
$\mathop{\mathrm{cd}}$ and $\overline{\mathop{\mathrm{cd}}}$.

######  Observation 4.8.

Let $W$, $W_{1}$ and $W_{2}$ be graphons such that $W=W_{1}+W_{2}$. Then
$\overline{\mathop{\mathrm{cd}}}(W)\geq\overline{\mathop{\mathrm{cd}}}(W_{1})+\overline{\mathop{\mathrm{cd}}}(W_{2})$
and
$\mathop{\mathrm{cd}}(W)\geq\mathop{\mathrm{cd}}(W_{1})+\mathop{\mathrm{cd}}(W_{2})$.

###### Proof.

We only prove the first inequality, as the second one can be deduced almost
identically. For any $f\in\mathcal{F}$, we have that

$\overline{\mathop{\mathrm{cd}}}(W,f)=\frac{1}{8}\int_{[0,1]^{4}}[W_{1}(x_{1},x_{2})+W_{2}(x_{1},x_{2})][W_{1}(x_{3},x_{4})+W_{2}(x_{3},x_{4})]I_{f}(x_{1},x_{2},x_{3},x_{4})\prod_{i=1}^{4}dx_{i}$
$\geq\frac{1}{8}\int_{[0,1]^{4}}[W_{1}(x_{1},x_{2})W_{1}(x_{3},x_{4})+W_{2}(x_{1},x_{2})W_{2}(x_{3},x_{4})]I_{f}(x_{1},x_{2},x_{3},x_{4})\prod_{i=1}^{4}dx_{i}$
$=\overline{\mathop{\mathrm{cd}}}(W_{1},f)+\overline{\mathop{\mathrm{cd}}}(W_{2},f)\geq\overline{\mathop{\mathrm{cd}}}(W_{1})+\overline{\mathop{\mathrm{cd}}}(W_{2}),$

and the result follows. ∎

This can be used to prove the following more interesting result.

######  Theorem 4.9.

Let $W$ be a graphon and $\mathcal{P}=\\{S_{1},S_{2},\dots,S_{n}\\}$ a
partition of the unit interval into measurable sets. Then, we have that
$\overline{\mathop{\mathrm{cd}}}(W)\leq\overline{\mathop{\mathrm{cd}}}(W_{\mathcal{P}})$
and $\mathop{\mathrm{cd}}(W)\leq\mathop{\mathrm{cd}}(W_{\mathcal{P}}).$

###### Proof.

The technique below was also used in the proof of Proposition 14.13 in [29].

By Lemma 4.5, we may assume that each $S_{i}$ is an interval. For every $i$,
let $a_{i}$ and $b_{i}$ be the endpoints of $S_{i}$ and let
$\phi_{i}:S_{i}\rightarrow S_{i}$ be the measure preserving map defined by
$\phi_{i}(x)=a_{i}+[2(x-a_{i})(\mod b_{i}-a_{i})]$. Let
$\phi:[0,1]\rightarrow[0,1]$ be the measure preserving map defined by
$\phi|_{S_{i}}=\phi_{i}$. The point of this is that the map from $S_{i}\times
S_{j}$ to itself given by $\phi(x,y)=(\phi(x),\phi(y))$ is ergodic for every
$i,j$. For every positive integer $n$, define a graphon $W_{n}$ with

$W_{n}(x,y)=\frac{1}{n}\sum_{t=0}^{n}W(\phi^{t}(x),\phi^{t}(y)).$

By Observation 4.8,

$\overline{\mathop{\mathrm{cd}}}(W_{n})\geq\frac{1}{n}\sum_{t=0}^{n}\overline{\mathop{\mathrm{cd}}}(W^{\phi^{t}})=\overline{\mathop{\mathrm{cd}}}(W).$

The sequence $W_{1},W_{2},\dots$ converges to $W_{\mathcal{P}}$ almost
everywhere by the choice of $\phi$, hence
$\overline{\mathop{\mathrm{cd}}}(W_{\mathcal{P}})=\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W_{n})\geq\overline{\mathop{\mathrm{cd}}}(W)$.
The result for crossing densities follows by an analogous argument. ∎

######  Corollary 4.10.

Let $p\in[0,1]$. Among all graphons $W$ with
$||W||_{1}=\int_{[0,1]^{2}}W(x,y)\ dx\ dy=p$, $W^{p}$ achieves the largest
crossing density, as well as the largest rectilinear crossing density.

It might seem inconvenient that the definitions of $\mathcal{F}$ and
$\mathcal{D}_{\mathcal{W}}$ allow for "degenerate" configurations. However, it
is possible to add several more restrictions to these families without
altering the crossing densities. Below, an example of this is provided.

We say that a function $f\in\mathcal{F}$ is nice if it is measure preserving
and bounded.

######  Theorem 4.11.

Let $W$ be a graphon. Then,

$\overline{\mathop{\mathrm{cd}}}(W)=\inf_{f}\overline{\mathop{\mathrm{cd}}}(W,f),$

where $f$ ranges over all nice elements of $\mathcal{F}$.

###### Proof.

Combining the ideas in the proofs of Theorems 4.3 and 4.4, we can obtain a
sequence $f_{1},f_{2},\dots$ of elements of $\mathcal{F}$, each of which
arises from a rectilinear drawing of a graph (as did $f_{\mathcal{D}}$ in our
proof that
$\overline{\mathop{\mathrm{cd}}}(W_{G})\leq\overline{\mathop{\mathrm{cd}}}+1/n$
for every $n$ vertex graph $G$), and such that
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W,f_{n})=\overline{\mathop{\mathrm{cd}}}(W)$.
For every maximal subinterval of $[0,1]$ that is mapped to a single point by
$f_{n}$, we can reconstruct $f_{n}$ so that its restriction to the subinterval
is instead measure preserving and its image is an arbitrarily small disk. This
modification can be carried out so that the rectilinear crossing density
increases by an arbitrarily small amount. Repeating this process for every
subinterval with the above property and then for every $n$, we arrive at a new
sequence $f_{1}^{\prime},f_{2}^{\prime},\dots$ of nice elements of
$\mathcal{F}$ such that
$\lim_{n\rightarrow\infty}\overline{\mathop{\mathrm{cd}}}(W,f_{n}^{\prime})=\overline{\mathop{\mathrm{cd}}}(W)$.
∎

We mentioned in the introduction that the crossing number of complete graphs
is connected to Sylvester’s four point problem. To finish this section, we
describe how this connection is, in some sense, a particular case of the
interplay between the rectilinear crossing density of graphons and the
rectilinear crossing number of graphs.

Given a bounded region $R\subset\mathbb{R}^{2}$ of positive measure, let
$\lambda_{R}$ be the probability measure that arises from restricting the
Lebesgue measure to $R$ and then normalizing. For any probability measure $P$
on the Lebesgue $\sigma$-algebra of $\mathbb{R}^{2}$, let $\text{c}(P)$ denote
the probability that four points sampled independently from $P$ can be labeled
by $a,b,c,d$ so that $I(a,b,c,d)=1$ (recall that $I$ was defined at the
beginning of this section). It was shown by Scheinerman and Wilf [38]
(although it is worded in a slightly different manner in their paper) that

$\lim_{n\rightarrow\infty}\frac{\overline{\mathop{\mathrm{cr}}}(K_{n})}{\binom{n}{4}}=\inf_{R}c(\lambda_{R}),$

where $R$ ranges over all bounded regions of positive measure.

Now, for $f\in\mathcal{F}$, let $\lambda_{f}$ denote the corresponding
pushforward probability measure on $\mathbb{R}^{d}$ (i.e.,
$\lambda_{f}(A)=\lambda(f^{-1}(A))$ for every measurable
$A\subseteq\mathbb{R}^{2}$). Every probability measure of the form
$\lambda_{R}$ is standard, and thus can be written as $\lambda_{f}$ for some
nice $f\in\mathcal{F}$. Furthermore, if $f$ is nice then
$\lambda_{f}=\lambda_{R}$ for some $R$. This implies that

$\inf_{f}c(\lambda_{f})=\inf_{R}c(\lambda_{R}),$

where $f$ ranges over all nice elements of $\mathcal{F}$. On top of this, it
is not hard to see that
$24\overline{\mathop{\mathrm{cd}}}(W^{1},f)=\text{c}(\lambda_{f})$ as long as
the set $f^{-1}(\ell)\subset[0,1]$ has measure $0$ for every line $\ell$ on
the plane. This observation, along with by Theorem 4.11, implies that

$24\overline{\mathop{\mathrm{cd}}}(W^{1})=\inf_{R}c(\lambda_{R}).$

By the first part of Corollary 4.6, this is actually equivalent to the result
of Scheinerman and Wilf.

##  5 Further research

Unlike the algorithm from [18], our drawing algorithm from Theorem 1.2 is not
deterministic. We leave the following open problem:

######  Problem 5.1.

Is there a deterministic polynomial-time algorithm that for every $n$-vertex
graph $G$ produces a drawing of $G$ with $\mathop{\mathrm{cr}}(G)+o(n^{4})$
crossings?

While Theorem 4.4 shows that the graphon parameters $\mathop{\mathrm{cd}}$ and
$\overline{\mathop{\mathrm{cd}}}$ are indeed the "correct" discrete analogs of
the rectilinear crossing density and the crossing density of graphs, there are
several ways in which we could have defined them. Indeed, as we exemplified at
the end of the previous section, minor tweaks to the definitions of
$\mathcal{F}$ and $\mathcal{D}_{\mathcal{W}}$ will often have no influence
whatsoever on the graphon parameters $\mathop{\mathrm{cd}}$ and
$\overline{\mathop{\mathrm{cd}}}$ (see Theorem 4.11). Since the definition of
$\mathcal{D}_{\mathcal{W}}$ is rather artificial (it is made up of all the
simple graphon drawings such that $I_{\mathcal{D}}$ measurable), it makes
sense to ask whether this family can be substituted for a more reasonable set
of functions from $[0,1]^{2}$ to $\mathcal{C}$ without altering
$\mathop{\mathrm{cd}}$.

The definition of a simple graphon drawing can also be modified to obtain
continuous analogs of other kinds of crossing numbers. For example, if we get
rid of condition $4$, we obtain a sort of pair crossing density101010The pair
crossing density of a graph $G$ is the least number of pairs of crossing edges
over all drawings of $G$. for graphons, while adding a fifth condition which
requires that each $\mathcal{D}(x,y)$ is $x$-monotone results in a monotone
crossing density111111A curve is $x$-monotone if every vertical line
intersects it in at most one point. A graph drawing is said to be monotone if
every edge is represented by an $x$-monotone curve. The monotone crossing
number of a graph is the least number of crossings that can be attained by a
monotone drawing.. Even though several of our arguments carry over to these
variants, we do not know whether a result along the lines of Theorem 3.3 holds
for other kinds of crossing numbers.

For any $p\in[0,1]$, the set of graphons with $||W||_{1}=p$ is clearly closed
with respect to $d_{\square}$. Since
$(\widetilde{\mathcal{W}_{0}},\delta_{\square})$ is compact and the crossing
densities are invariant, the following problem makes sense.

######  Problem 5.2.

For every $p\in[0,1]$, determine two graphon $W_{1}$ and $W_{2}$ with
$||W_{1}||_{1}=||W_{2}||_{1}=p$ such that

$\overline{\mathop{\mathrm{cd}}}(W_{1})=\min_{W\in\mathcal{W}_{0},||W||_{1}=p}\overline{\mathop{\mathrm{cd}}}(W)$

and

$\mathop{\mathrm{cd}}(W_{2})=\min_{W\in\mathcal{W}_{0},||W||_{1}=p}\mathop{\mathrm{cd}}(W).$

Corollary 4.10 provides a solution to the variant of this problem where the
minimums are substituted by maximums. We expect both of the above questions to
be difficult to answer.

## References

  * [1] Bernardo M Ábrego, Mario Cetina, Silvia Fernández-Merchant, Jesús Leaños, and Gelasio Salazar.  On $\leq k$-edges, crossings, and halving lines of geometric drawings of ${K}_{n}$.  Discrete & Computational Geometry, 48(1):192–215, 2012.
  * [2] Miklós Ajtai, Vasek Chvátal, Monty Newborn, and Endre Szemerédi.  Crossing-free subgraphs.  North-holland Mathematics Studies, 60:9–12, 1982.
  * [3] Sanjeev Arora, Satish Rao, and Umesh Vazirani.  Expander flows, geometric embeddings and graph partitioning.  Journal of the ACM (JACM), 56(2):1–37, 2009.
  * [4] József Balogh and Gelasio Salazar.  k-sets, convex quadrilaterals, and the rectilinear crossing number of $k_{n}$.  Discrete & Computational Geometry, 35(4):671–690, 2006.
  * [5] MARK DE BERG and Otfried Schwarzkopf.  Cuttings and applications.  International Journal of Computational Geometry & Applications, 5(04):343–355, 1995.
  * [6] Sandeep N Bhatt and Frank Thomson Leighton.  A framework for solving VLSI graph layout problems.  Journal of Computer and System Sciences, 28(2):300–343, 1984.
  * [7] Daniel Bienstock.  Some provably hard crossing number problems.  In Proceedings of the sixth annual symposium on Computational geometry, pages 253–260, 1990.
  * [8] Daniel Bienstock and Nathaniel Dean.  Bounds for rectilinear crossing numbers.  Journal of Graph theory, 17(3):333–348, 1993.
  * [9] Christian Borgs, Jennifer T Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi.  Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing.  Advances in Mathematics, 219(6):1801–1851, 2008.
  * [10] Bernard Chazelle.  Cuttings.  In Handbook of Data Structures and Applications, pages 397–404. Chapman and Hall/CRC, 2018.
  * [11] Fan R. K. Chung, Ronald L. Graham, and Richard M. Wilson.  Quasi-random graphs.  Combinatorica, 9(4):345–362, 1989.
  * [12] Julia Chuzhoy.  An algorithm for the graph crossing number problem.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 303–312, 2011.
  * [13] Julia Chuzhoy, Sepideh Mahabadi, and Zihan Tan.  Towards better approximation of graph crossing number.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 73–84. IEEE, 2020.
  * [14] Julia Chuzhoy, Yury Makarychev, and Anastasios Sidiropoulos.  On graph crossing number and edge planarization.  In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms, pages 1050–1069. SIAM, 2011.
  * [15] Domingos Dellamonica, Subrahmanyam Kalyanasundaram, Daniel M Martin, VOJTĚCH RÖDL, and Asaf Shapira.  An optimal algorithm for finding frieze–kannan regular partitions.  Combinatorics, Probability and Computing, 24(2):407–437, 2015.
  * [16] Guy Even, Sudipto Guha, and Baruch Schieber.  Improved approximations of crossings in graph drawings and VLSI layout areas.  SIAM Journal on Computing, 32(1):231–252, 2002.
  * [17] Ruy Fabila-Monroy and Jorge López.  Computational search of small point sets with small rectilinear crossing number.  arXiv preprint arXiv:1403.1288, 2014.
  * [18] Jacob Fox, János Pach, and Andrew Suk.  Approximating the rectilinear crossing number.  In International Symposium on Graph Drawing and Network Visualization, pages 413–426. Springer, 2016.
  * [19] Alan Frieze and Ravi Kannan.  Quick approximation to matrices and applications.  Combinatorica, 19(2):175–220, 1999.
  * [20] Michael R Garey and David S Johnson.  Crossing number is np-complete.  SIAM Journal on Algebraic Discrete Methods, 4(3):312–316, 1983.
  * [21] Oded Goldreich and Luca Trevisan.  Three theorems regarding testing graph properties.  Random Structures & Algorithms, 23(1):23–57, 2003.
  * [22] William T Gowers.  Lower bounds of tower type for szemerédi’s uniformity lemma.  Geometric & Functional Analysis GAFA, 7(2):322–337, 1997.
  * [23] Richard K Guy.  A combinatorial problem.  Nabla (Bulletin of the Malayan Mathematical Society), 7(68-72):8, 1960.
  * [24] Ken-ichi Kawarabayashi and Anastasios Sidiropoulos.  Polylogarithmic approximation for minimum planarization (almost).  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 779–788. IEEE, 2017.
  * [25] Ken-ichi Kawarabayashi and Anastasios Sidiropoulos.  Polylogarithmic approximation for euler genus on bounded degree graphs.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 164–175, 2019.
  * [26] Frank Thomson Leighton.  Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks.  MIT Press, Cambridge, MA, USA, 1983.
  * [27] Tom Leighton and Satish Rao.  Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.  Journal of the ACM (JACM), 46(6):787–832, 1999.
  * [28] Richard J Lipton and Robert Endre Tarjan.  A separator theorem for planar graphs.  SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.
  * [29] László Lovász.  Large networks and graph limits, volume 60.  American Mathematical Soc., 2012.
  * [30] László Lovász and Balázs Szegedy.  Szemerédi’s lemma for the analyst.  GAFA Geometric And Functional Analysis, 17(1):252–270, 2007.
  * [31] László Lovász, Katalin Vesztergombi, Uli Wagner, and Emo Welzl.  Convex quadrilaterals and k-sets.  Contemporary Mathematics, 342:139–148, 2004.
  * [32] Gary L Miller.  Finding small simple cycle separators for 2-connected planar graphs.  In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 376–382, 1984.
  * [33] John W Moon.  On the distribution of crossings in random complete graphs.  Journal of the Society for Industrial and Applied Mathematics, 13(2):506–510, 1965.
  * [34] János Pach and Gábor Tardos.  Untangling a polygon.  In International Symposium on Graph Drawing, pages 154–161. Springer, 2001.
  * [35] János Pach and Géza Tóth.  Thirteen problems on crossing numbers.  Geombinatorics, 9(4):194–207, 2000.
  * [36] Richard E Pfiefer.  The historical development of J.J. Sylvester’s four point problem.  Mathematics Magazine, 62(5):309–317, 1989.
  * [37] Marcus Schaefer.  The graph crossing number and its variants: A survey.  The electronic journal of combinatorics, pages DS21–Apr, 2012.
  * [38] Edward R Scheinerman and Herbert S Wilf.  The rectilinear crossing number of a complete graph and sylvester’s “four point problem” of geometric probability.  The American mathematical monthly, 101(10):939–943, 1994.
  * [39] Joel Spencer and Géza Tóth.  Crossing numbers of random graphs.  Random Structures & Algorithms, 21(3-4):347–358, 2002.
  * [40] Endre Szemerédi.  Regular partitions of graphs.  Technical report, Stanford Univ Calif Dept of Computer Science, 1975.
  * [41] Roberto Tamassia.  Handbook of graph drawing and visualization.  CRC press, 2013.
  * [42] Peter Ungar.  A theorem on planar graphs.  Journal of the London Mathematical Society, 1(4):256–262, 1951.