1 Introduction

The crossing number of a graph G, denoted by \(\mathrm {cr}(G)\), is the smallest number of pairwise edge crossings over all possible drawings of G. Many papers are devoted to the study of this parameter, refer to [22, 25] for surveys. In particular, minimizing the number of crossings is one of the seminal problems in graph drawing (see, e.g., [2, 3, 23]), whose importance has been further witnessed by user studies showing how edge crossings may deteriorate the readability of a diagram [20, 21, 26]. On the other hand, determining the crossing number of a graph is NP-hard [5] and can be solved exactly only on small/medium instances [7]. On the positive side, the crossing number is fixed-parameter tractable in the number of crossings [15] and can be approximated by a constant factor for graphs of bounded degree and genus [10].

A recent research stream studies graph drawings where, rather than minimizing the number of crossings, some edge crossing patters are forbidden; refer to [4, 9, 11, 12] for surveys and reports. A key motivation for the study of so-called beyond-planar graphs are recent cognitive experiments showing that already the absence of specific kinds of edge crossing configurations has a positive impact on the human understanding of a graph drawing [13, 18]. Of particular interest for us are three families of beyond-planar graphs that have been extensively studied, namely the k-planar, fan-planar, and k-quasi-planar graphs; refer to [9] for additional families. A k-planar drawing is such that each edge is crossed at most \(k \ge 1\) times [19] (see also [16] for a survey on 1-planarity). A k-quasi planar drawing does not have \(k \ge 3\) mutually crossing edges [1]. A fan-planar drawing does not contain two independent edges that cross a third one or two adjacent edges that cross another edge from different “sides” [14]. A graph is k-planar (k-quasi-planar, fan-planar) if it admits a k-planar (k-quasi-planar, fan-planar) drawing; a 3-quasi-planar graph is simply called quasi-planar.

Table 1. Lower and upper bounds the crossing ratio of beyond-planar graphs.
Full size table

In this context, an intriguing question is to what extent edge crossings can be minimized while forbidding such local crossing patterns. In particular, we ask whether avoiding local crossing patterns in a drawing of a graph may enforce an overall large number of crossings, whereas only a few crossings would suffice in a crossing-minimal drawing of the graph. We answer this question in the affirmative for the above-mentioned three families of beyond-planar graphs. Our contribution are summarized in Table 1.

  1. 1.

    In Sect. 2, we prove that there exist n-vertex 1-planar graphs such that the ratio between the minimum number of crossings in a 1-planar drawing of one such graph and its crossing number is \(n/2-1\). This result can be easily extended to k-planar graphs if we allow parallel edges.

  2. 2.

    In Sect. 3, we prove that there exist n-vertex quasi-planar graphs such that the ratio between the minimum number of crossings in a quasi-planar drawing of one such graph and its crossing number is \(\varOmega (n)\). Similarly, a \(\varOmega (n/k^3)\) bound can be proved for k-quasi-planar graphs.

  3. 3.

    In Sect. 4, we prove that there exist n-vertex fan-planar graphs such that the ratio between the minimum number of crossings in a fan-planar drawing of one such graph and its crossing number is \(\varOmega (n)\).

The lower bound in Result 1 is tight. Since fan-planar and quasi-planar graphs have \(\mathcal {O}(n)\) edges, the lower bounds in Results 2 and 3 are a linear factor from the trivial upper bound \(\mathcal {O}(n^2)\), and it remains open whether such an upper bound can be achieved (see Sect. 5). All results are based on nontrivial constructions that exhibit interesting structural properties of the investigated graphs.

Notation and Definitions. We assume familiarity with standard definitions about graph drawings and embeddings of planar and nonplanar graphs (see, e.g., [8, 9]). In a drawing of a graph, we assume that an edge does not contain a vertex other than its endpoints, no two edges meet tangentially, and no three edges share a crossing. It suffices to only consider simple drawings where any two edges intersect in at most one point, which is either a common endpoint or an interior point where the two edges properly cross. Thus, in a simple drawing, any two adjacent edges do not cross and any two non-adjacent edges cross at most once.

We define the k-planar crossing number of a k-planar graph G, denoted by \(\mathrm {cr}_{k\text {-pl}}(G)\), as the minimum number of crossings over all k-planar drawings of G. The k-planar crossing ratio \(\varrho _{k\text {-pl}}\) is the supremum of \(\mathrm {cr}_{k\text {-pl}}(G)/\mathrm {cr}(G)\) over all k-planar graphs G. Analogously, we define the quasi-planar and the fan-planar crossing number of a graph G, denoted by \(\mathrm {cr}_\text {quasi}(G)\) and \(\mathrm {cr}_\text {fan}(G)\), as well as the quasi-planar and the fan-planar crossing ratio, denoted by \(\varrho _\text {quasi}\) and \(\varrho _\text {fan}\).

2 The 1-planar Crossing Ratio

An n-vertex 1-planar graph has at most \(4n-8\) edges and a 1-planar drawing has at most \(n-2\) crossings, that is \(\mathrm {cr}_\text {1-pl}(G) \le n-2\) [16]. Observe that for \(\mathrm {cr}(G) < \mathrm {cr}_\text {1-pl}(G)\) it has to hold that \(\mathrm {cr}(G) \ge 2\). It follows that the 1-planar crossing ratio is \(\varrho _\text {1-pl}\le n/2-1\). We show that this bound can be achieved.

Theorem 1

For every \(\ell \ge 7\), there exists a 1-planar graph \(G_\ell \) with \(n=11\ell +2\) vertices such that \(\mathrm {cr}_\text {1-pl}(G_\ell )=n-2\) and \(\mathrm {cr}(G_\ell )=2\), which yields the largest possible 1-planar crossing ratio.

The construction of \(G_\ell \) consists of three parts: a rigid graph P that has to be drawn planar in any 1-planar drawing; its dual \(P^*\); a set of binding edges and one special edge that force P and \(P^*\) to be intertwined in any 1-planar drawing.

To obtain P, we utilize a construction introduced by Korzhik and Mohar [17]. They construct graphs \(H_\ell \) that are the medial extension of the Cartesian product of the path of length 2 and the cycle of length \(\ell \); see Fig. 1a. They prove that \(H_\ell \) has exactly one 1-planar embedding on the sphere, and that embedding is crossing-free. We choose \(P=H_{\ell }\) as our rigid graph and fix its (1−) planar embedding (when we will refer to P, we will usually mean this embedding).

Let \(P^*\) be the dual of P, obtained by placing a dual vertex \(h^*\) into each face h of P and connecting two dual vertices if their corresponding faces share an edge; see Fig. 1b. Since P has \(5\ell \) vertices and \(11\ell \) edges, by Euler’s polyhedra formula it has \(6\ell +2\) faces; thus, \(P^*\) has \(6\ell +2\) vertices and \(11\ell \) edges.

Obviously, \(P\cup P^*\) can be drawn planar, as both P and \(P^*\) are planar and disjoint. All faces of P have size 3 or 4, except two large (called polar) faces f and g of size \(\ell \). We create a graph \(G'\) by adding \(\ell \) binding edges to \(P\cup P^*\) between \(f^*\) (the vertex of \(P^*\) corresponding to face f) and the vertices of P that are incident to f. This forces \(f^*\) to be drawn in face f in any 1-planar drawing.

In the full version [6] we prove the following lemma, cf. Fig. 1c and d.

Fig. 1.
figure 1

Construction of the graph \(G_\ell \) in the proof of Theorem 1. Blue circles and edges are P; red squares and bold edges are \(P^*\); green dashed edges are the binding edges; and the orange very bold edge is the special edge. (Color figure online)

Full size image

Lemma 2

\(G'\) has only two types of 1-planar embeddings (up to the choice of the outer face): a planar one where \(P^*\) lies completely inside face f of P; and a 1-planar embedding where \(f^*\) lies inside f, \(g^*\) lies inside g, and each edge of P crosses an edge of \(P^*\) and vice versa.

Let z be a vertex of P on the boundary of f. Let y be the face of size 4 that has z on its boundary. Let x be the degree-6 vertex on the boundary of y. We obtain \(G_\ell \) from \(G'\) by adding the special edge \((x,y^*)\). In the planar embedding of Lemma 2, \(P^*\) and thus \(y^*\) lies inside face f of P, so \((x,y^*)\) has to cross at least two edges of P; see Fig. 1d. Choosing the face that corresponds to z as the outer face of \(P^*\) gives a non-1-planar drawing of \(G_\ell \) with 2 crossings.

Hence, \(G'\) has to be drawn in the second way of Lemma 2; see Fig. 1c. Here, the edge \((x,y^*)\) can be added without further crossings. Graph \(G_\ell \) consists of \(n=11\ell +2\) vertices in total. Both P and \(P^*\) have \(11\ell \) edges, and each of them is crossed, so there are \(n-2\) crossings in total, which is the maximum possible in a 1-planar drawing. Hence, \(\mathrm {cr}_\text {1-pl}(G_\ell )=n-2\) and \(\mathrm {cr}(G_\ell )=2\), so \(\varrho _\text {1-pl}\le n/2-1\).

The construction used in the proof of Theorem 1 can be generalized to k-planar multigraphs. It suffices to replace each edge of \(G_\ell \), except the special edge, by a bundle of k parallel edges:

Corollary 3

For every \(\ell \ge 6\), there exists a k-planar multigraph \(G_{\ell ,k}\) with \(n=11\ell +2\) vertices and maximum edge multiplicity k such that \(\mathrm {cr}_k\text {-pl}(G_{\ell ,k})=k^2\,(n-2)\) and \(\mathrm {cr}(G_{\ell ,k})=2k\), thus \(\varrho _k\text {-pl}\ge k\,(n-2)/2\).

3 The Quasi-planar Crossing Ratio

An n-vertex quasi-planar graph G has at most \(6.5n-20\) edges, thus \(\mathrm {cr}_\text {quasi}(G) \in \mathcal {O}(n^2)\) [9]. For \(\mathrm {cr}(G) < \mathrm {cr}_{\text {quasi}}\) it has to hold that \(\mathrm {cr}(G) \ge 2\), and hence \(\varrho _\text {quasi}\in \mathcal {O}(n^2)\). We show that the quasi-planar crossing ratio is unbounded, even for \(\mathrm {cr}(G)\le 3\):

Theorem 4

For every \(\ell \ge 2\), there exists a quasi-planar graph \(G_\ell \) with \(n=12\ell -5\) vertices such that \(\mathrm {cr}_{{quasi}}(G_\ell ) \ge \ell \) and \(\mathrm {cr}(G_\ell ) \le 3\), thus \(\varrho _{{quasi}} \in \varOmega (n)\).

In order to prove Theorem 4, we begin with a technical lemma.

Lemma 5

Let G be a graph containing two independent edges (u, v) and (w, z). Suppose that u and v (w and z, resp.) are connected by a set \(\varPi _{uv}\) (\(\varPi _{wz}\), resp.) of \(\ell -1\) paths of length two. Let \(\varGamma \) be a drawing of G. If (u, v) and (w, z) cross in \(\varGamma \), then \(\varGamma \) contains at least \(\ell \) crossings.

Proof

Suppose that (u, v) and (w, z) cross. If each of the \(\ell -1\) paths in \(\varPi _{wz}\) crosses (u, v), then the claim follows. Assume otherwise that at least one of these paths does not cross (u, v). This path forms a 3-cycle t with (w, z); the \(\ell -1\) paths of \(\varPi _{uv}\) all cross at least one edge of t, which proves the claim.    \(\square \)

Fig. 2.
figure 2

Illustration for the proof of Theorem 4.

Full size image

Proof

(of Theorem 4). Let \(G_\ell \) be the graph constructed as follows; cf. Fig. 2a. Start with a 6-cycle \(C=\langle u_0,u_1,\dots ,u_5 \rangle \), and a vertex x connected to each of C, yielding graph \(G'\). Extend each edge of \(G'\) by adding \(\ell -1\) disjoint paths of length two between its endpoints. Finally, add special edges \((u_i,u_{i+3})\), \(i=0,1,2\).

The resulting graph \(G_\ell \) has \(n=12(\ell -1)+7=12\ell -5\) vertices and admits a drawing with 3 crossings, so \(\mathrm {cr}(G_\ell ) \le 3\); see Fig. 2a. Note that \(G_\ell \) admits a quasi-planar drawing with \(2\ell +1\) crossings as shown in Fig. 2b. We prove that \(\mathrm {cr}_\text {quasi}(G_\ell ) \ge \ell \). Let \(\varGamma \) be a quasi-planar drawing of \(G_\ell \). If there are two edges of \(G'\) that cross each other, then the claim follows by Lemma 5.

If no special edge would cross \(G'\), they would all be drawn within the unique face of size 6 in \(G'\). They would mutually cross, contradicting quasi-planarity.

Thus, at least one special edge, say \(s=(u_0,u_3)\), crosses an edge (a, b) of \(G'\). Consider the closed (possibly self-intersecting) curve \(\mathcal L\) composed of s plus the subpath of C connecting \(u_0\) to \(u_3\) and containing none of the vertices a and b. This curve partitions the plane into two or more regions, and a and b lie in different regions; see Fig. 2c and d for an illustration. Thus (a, b) and the \(\ell -1\) paths connecting a and b cross \(\mathcal L\), yielding \(\ell \) crossings in \(\varGamma \), as desired.    \(\square \)

The above proof can be straight-forwardly extended to k-quasi-planar graphs by using exactly the same construction in which the cycle C has length 2k. Note that any k-quasi-planar graph has at most \(c_k n\log n\) edges, where \(c_k\) depends only on k [24], so \(\varrho _\text {quasi}\le f(k)\cdot n^2\log ^2 n\).

Corollary 6

For every \(\ell \ge 2\) and \(k \ge 3\), there exists a k-quasi-planar graph \(G_{\ell ,k}\) with \(n=2k(\ell +1)+1\) vertices such that \(\mathrm {cr}_{{quasi}}(G_{\ell ,k}) \ge \ell \) and \(\mathrm {cr}(G_{\ell ,k}) \le k(k-1)/2\), thus \(\varrho _{{quasi}} \in \varOmega (n/k^3)\).

4 The Fan-Planar Crossing Ratio

An n-vertex fan-planar graph G has at most \(5n-10\) edges, thus \(\mathrm {cr}_\text {fan}(G) \in \mathcal {O}(n^2)\) [9]. For \(\mathrm {cr}(G) < \mathrm {cr}_\text {fan}(G)\) it has to hold that \(\mathrm {cr}(G) \ge 2\), and hence \(\varrho _\text {fan}\in \mathcal {O}(n^2)\). We show that the fan-planar crossing ratio is unbounded, even for \(\mathrm {cr}(G)=3\).

Theorem 7

For every \(\ell \ge 2\), there exists a fan-planar graph \(G_\ell \) with \(n=9\ell +1\) vertices such that \(\mathrm {cr}_\text {fan}(G_\ell ) = \ell \) and \(\mathrm {cr}(G_\ell )=3\), thus \(\varrho _\text {fan}\in \varOmega (n)\).

Fig. 3.
figure 3

Illustration for the proof of Theorem 7.

Full size image

Proof

Let \(G_\ell \) be the graph constructed as follows; cf. Fig. 3a. Start with a \(K_{3,3}\). Extend each edge of the \(K_{3,3}\) by adding \(\ell -1\) disjoint paths of length two between its endpoints, except for two independent edges (u, v) and (w, z). Add vertices \(w'\) and \(z'\), edges \(\bar{w}=(w,w')\) and \(\bar{z}=(z,z')\), \(\ell \) disjoint paths of length two connecting \(w'\) and z, and \(\ell \) disjoint paths of length two connecting \(z'\) and w.

Graph \(G_\ell \) has \(n=6+7(\ell -1)+2+2\ell =9\ell +1\) vertices and admits a drawing with three crossings, see Fig. 3a. Recall that we obtain a subdivision of a graph G by subdividing (even multiple times) any subset of its edges. \(G_\ell \) contains three subdivisions of \(K_{3,3}\) sharing only edge (u, v), and thus each subdivision requires at least one distinct crossing in any drawing. It follows that \(\mathrm {cr}(G_\ell )=3\). Note that \(G_\ell \) admits a fan-planar drawing with \(\ell \) crossings, cf. Fig. 3b. We prove that \(\mathrm {cr}_\text {fan}(G_\ell ) = \ell \). Let \(\Gamma \) be a fan-planar drawing of \(G_\ell \). If any two extended edges cross each other, then the claim follows by Lemma 5. Assume they do not:

\(G_\ell \) contains \(\ell \) subdivions of \(K_{3,3}\) that share only (u, v) and \(\bar{w}\). Since each \(K_{3,3}\) subdivision requires at least one crossing, there are either \(\ell \) crossings in \(\Gamma \) (proving the claim), or (u, v) crosses \(\bar{w}\). Similarly, \(G_\ell \) contains \(\ell \) \(K_{3,3}\) subdivisions that share only (u, v) and \(\bar{z}\), and we can assume that (u, v) crosses \(\bar{z}\). But fan-planarity forbids (u, v) to cross both \(\bar{w}\) and \(\bar{z}\).    \(\square \)

5 Open Problems

The main open question is whether there exist fan-planar and quasi-planar graphs whose crossing ratio is \(\varOmega (n^2)\). In fact, we conjecture that this bound can be reached, but proving our suspected constructions turns out to be elusive. Another natural research direction is to extend our results to further families of beyond-planar graphs, such as k-gap planar graphs or fan-crossing-free graphs (refer to [9] for definitions). Finally, we may ask whether similar lower bounds can be proved in the geometric setting (i.e., when the edges are drawn as straight-line segments).