Gap-Planar Graphs

Abstract

We introduce the family of k-gap-planar graphs for $k \ge 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition finds motivation in edge casing, as a $k$-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs.

Research started at the NII Shonan Meeting “Algorithmics for Beyond Planar Graphs.” The authors thank the organizers, and Yota Otachi for useful discussions. Bae was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2015R1D1A1A01057220). Baffier was supported by JST-ERATO Grant Number JPMJER1201, Japan. Eades and Hong were partially supported by ARC DP160104148. Korman was partially supported by MEXT KAKENHI No. 15H02665, 17K12635 and JST ERATO Grant Number JPMJER1305. Tóth was supported in part by the NSF awards CCF-1422311 and CCF-1423615.

1 Introduction

“Beyond-planar graphs” are informally defined as nonplanar graphs that can be represented with some forbidden edge crossing patterns (see, e.g., [29, 30, 36]). Research on this topic is attracting increasing attention within the communities of graph theory, graph algorithms, graph drawing, and computational geometry, as these graphs represent a natural generalization of planar graphs, and their study can provide significant insights for the design of effective methods to visualize real-world networks. Indeed, the motivation for this line of research stems from both the interest raised by the combinatorial and geometric properties of these graphs, and experiments showing how the absence of particular edge crossing patterns has a positive impact on the readability of a graph drawing [31].

Among the investigated families of beyond-planar graphs are: k -planar graphs (see, e.g., [11, 34, 38]), which can be drawn with at most $k>0$ crossings per edge; k -quasiplanar graphs (see, e.g., [2, 3, 22]), where there are no $k>2$ pairwise crossing edges; fan-planar graphs (see, e.g., [9, 12, 32]), where no edge can be crossed by two indepedent edges; fan-crossing-free graphs [17], where crossings between an edge and two adjacent edges are forbidden; planarly-connected graphs [1], in which each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints; RAC graphs (refer, e.g., to [19]), which admit a straight-line (or polyline with few bends) drawing with right-angle crossings.

Fig. 1.

(a) A drawing of a graph G and (b) its cased version where each edge is interrupted at most twice, i.e., a $2$-gap-planar drawing of G.

In this paper we introduce k-gap-planar. Intuitively speaking, each crossing is assigned to one of the two involved edges and each edge is assigned at most k crossings (see Sect. 2). This definition generalizes that of k-planar graphs, and it is practically motivated by edge casing, a method commonly used to alleviate the visual clutter generated by crossing lines in a diagram [5, 21]. In a cased drawing of a graph, each crossing is resolved by locally interrupting one of the two crossing edges. Clearly, minimizing the number of gaps per edge is one of the desirable goals in this situation, and a $k$-gap-planar graph can be equivalently defined as a graph that admits a cased drawing in which each edge has at most k gaps. Figure 1 shows a drawing of a graph and its version with edge casing. Eppstein et al. [21] studied many optimization problems related to edge casing, assuming the input to be a drawing (rather than a graph). In particular, the problem of minimizing the maximum number of gaps (called tunnels) for any edge of a drawing can be solved in polynomial time (see also Sect. 2). We also remark that a similar drawing paradigm is used by partial edge drawings (PEDs), in which the central part of each edge is erased, while the two remaining stubs are required to be crossing-free (see, e.g., [15, 16]).

Our results can be summarized as follows:

• Every $k$-gap-planar graph with n vertices has $O(\sqrt{k} \cdot n)$ edges (Sect. 3). If $k=1$, a bound of $5n-10$ edges is proved for $1$-gap-planar multigraphs, which is tight as there exist $k$-gap-planar (simple) graphs with these many edges. Note that this density bound equals that of 2-planar graphs [38].

• The complete graph $K_n$ is $1$-gap-planar if and only if $n \le 8$ (Sect. 4).

• Deciding whether a graph is $1$-gap-planar is NP-complete, even when the input graph comes with a fixed rotation system that is part of the input (Sect. 5). We remark that analogous recognition problems for other families of beyond-planar graphs are also NP-hard (see, e.g., [7, 9, 12, 13, 25, 35]), while polynomial algorithms are known only in restricted settings (see, e.g., [6, 9, 13, 18, 20, 27, 28]).

• We study relationships of the $k$-gap-planar family with other beyond-planar families. For all $k \ge 1$, the class of 2k-planar graphs is properly included in the class of $k$-gap-planar graphs, which in turn is properly included in the $(2k+2)$-quasiplanar graphs (Sect. 6). It is worth observing that recent papers proved that k-planar graphs are $(k+1)$-quasiplanar [4, 26].

For reasons of space some proofs and technicalities have been omitted and can be found in [8].

2 Preliminaries and Basic Results

A drawing $\varGamma$ of a graph $G=(V,E)$ is a mapping of the vertices of V to distinct points of the plane, and of the edges of E to Jordan arcs connecting their corresponding endpoints but not passing through any other vertex. If two edges are incident to the same vertex, then they do not cross in $\varGamma$; else, they have at most one common interior point where they cross transversely. For a subset $E' \subseteq E$, $\varGamma [E']$ denotes the restriction of $\varGamma$ to the curves representing the edges of $E'$. Drawing $\varGamma$ is planar if no edge is crossed. The crossing number $\mathrm{cr}(G)$ of a graph G is the smallest number of edge crossings over all drawings of G. A graph is planar if it admits a planar drawing. A planar drawing subdivides the plane into topologically connected regions, called faces. The unbounded region is the outer face. A planar embedding of a planar graph G is an equivalence class of topologically equivalent drawings of G. A plane graph is a planar graph with a planar embedding. The crossing graph $C(\varGamma )$ of a drawing $\varGamma$ is the graph having a vertex $v_e$ for each edge e of G, and an edge $(v_e,v_f)$ if and only if edges e and f cross in $\varGamma$. The planarization $\varGamma ^*$ of $\varGamma$ is the plane graph formed from $\varGamma$ by replacing each crossing by a dummy vertex. To avoid ambiguities, we call real vertices the vertices of $\varGamma ^*$ that are not dummy.

Let $\varGamma$ be a drawing of a graph G. We shall assume that exactly two edges of G cross in one point p of $\varGamma$, and we say that these two edges are responsible for p. A k-gap assignment of $\varGamma$ maps each crossing point of $\varGamma$ to one of its two responsible edges so that each edge is assigned with at most k of its crossings; see, e.g., Fig. 1(b). The gap of an edge is the number of crossings assigned to it. An edge with at least one gap is gapped, or a gap edge, else it is gap free. A drawing is k-gap-planar if it admits a $k$-gap assignment. A graph is k-gap-planar if it has a $k$-gap-planar drawing. Note that the 0-gap-planar graphs coincide with the planar graphs, and that k-gap-planarity is a monotone property: every subgraph of a $k$-gap-planar graph is $k$-gap-planar. From the pigeonhole principle we have:

Property 1

Let $\varGamma$ be a $k$-gap-planar drawing of a graph $G=(V,E)$. For any $E' \subseteq E$, $\varGamma [E']$ contains at most $k \cdot |E'|$ crossings.

A $k$-gap assignment of a drawing $\varGamma$ corresponds to orienting the edges of the crossing graph $C(\varGamma )$ such that each vertex has indegree at most k (intuitively, orienting a crossing towards an edge means we assign the crossing to that edge). Since finding a lowest indegree orientation of a graph corresponds to finding its pseudoarboricity [23, 39], Property 2 follows. A pseudoforest is a graph in which every connected component has at most one cycle, and the pseudoarboricity of a graph is the smallest number of pseudoforests needed to cover all its edges.

Property 2

A graph is $k$-gap-planar if and only if it admits a drawing whose crossing graph has pseudoarboricity at most k.

Given a drawing $\varGamma$ of a graph $G=(V,E)$, finding the minimum k such that $\varGamma$ is $k$-gap-planar can be solved in $O(|E|^4)$ time, due to the fact that finding a lowest indegree orientation of $C(\varGamma )$ can be solved in time quadratic in the number of edges of $C(\varGamma )$ [40].

3 Density of $k$-gap-planar Graphs

We begin with an upper bound on the number of edges of $k$-gap-planar graphs.

Theorem 1

A $k$-gap-planar graph on $n \ge 3$ vertices has $O(\sqrt{k}\cdot n)$ edges.

Proof

The crossing number of a graph G with n vertices and m edges is bounded by $\mathrm{cr}(G)\ge \frac{1024}{31827}\cdot m^3/n^2$ when $m\ge \frac{103}{6}n$ [37]. Combined with the bound $\mathrm{cr}(G)\le k \cdot m$ (Property 1), we obtain

$$\frac{1024}{31827}\cdot \frac{m^3}{n^2}\le \mathrm{cr}(G)\le km,$$

which implies $m\le \max (5.58 \sqrt{k},17.17)\cdot n$, as required.   $\square$

Better upper bounds are possible for small values of k, in particular for $k=1$. Pach et al. [37] proved that a graph G with $n\ge 3$ vertices satisfies $\mathrm{cr}(G)\ge \frac{7}{3}m-\frac{25}{3}(n-2)$. Combined with the bound $\mathrm{cr}(G)\le k \cdot m$, we have

$$m\le \frac{25(n-2)}{7-3k}.$$

For $k=1$ (i.e., for $1$-gap-planar graphs), this gives $m\le 6.25n-12.5$. We now show how to improve this bound to $m\le 5n-10$. The idea is to follow a strategy developed by Pach and Tóth [38] and Bekos et al. [11] on the density of 2- and 3-planar graphs, with several important differences.

We start by stating the assumptions and notations for the proof of Theorem 2. In order to accommodate the elementary operations in the proof, we work on a broader class of graphs, namely multigraphs admitting a drawing without homotopic¹ parallel edges.

(i) For any $n\in \mathbb {N}$, $n\ge 3$, let $G=(V,E)$ be a $1$-gap-planar multigraph with n vertices that has the maximum number of edges possible over all n-vertex $1$-gap-planar multigraphs without homotopic parallel edges; (ii) let $\varGamma$ be a $1$-gap-planar drawing of G with the minimum number of edge crossings over all possible $1$-gap-planar drawings of G with non-homotopic parallel edges; and (iii) let $H=(V,E')$ be a sub-multigraph of G, where $E'\subseteq E$ is a multiset of edges that are pairwise noncrossing in $\varGamma [E']$. (iv) We assume that over all choices of G, $\varGamma$, and H described above, the multigraph H is maximum and, in case of ties, has the fewest connected components.

Our proof is based on the next technical lemma.

Lemma 1

The multigraph H is a triangulation, that is, a plane multi-graph in which every face is bounded by a walk with three vertices and three edges.

We can now show that $|E|\le 5n-10$.

Theorem 2

A $1$-gap-planar graph on $n \ge 3$ vertices has at most $5n-10$ edges.

Proof

By Lemma 1, we know that $H=(V,E')$ is a triangulation. By Euler’s polyhedron theorem, it has $3n-6$ edges and $2n-4$ triangular faces. Consider the edges in $E''=E\setminus E'$. It remains to show that $|E''|\le 2n-4$.

The embedding of edge $e\in E''$ is a Jordan arc that visits two or more triangle faces of H. We call the first and last triangles along e the end triangles of e. For an end triangle $\varDelta$, the connected component of $e\cap \varDelta$ incident to a vertex of $\varDelta$ is called an end portion. We use the following charging scheme.

Each edge $e\in E''$ charges one unit to a triangle face of H. If e has an end portion that has a gap neither in the interior nor on the boundary of the corresponding end triangle $\varDelta$, then e charges one unit to $\varDelta$. (If neither end portions of e has a gap in the interior or on the boundary of its end triangle, then e charges one arbitrary end triangle.) Otherwise the two end portions of e lie in two adjacent triangles, say, $\varDelta _1$ and $\varDelta _2$, and e uses its gap to cross the common edge on the boundary between them; in this case e charges one unit to $\varDelta _1$ or $\varDelta _2$ as follows: If the gap of the common edge between $\varDelta _1$ and $\varDelta _2$ is used for an end portion of $e'\cap \varDelta _1$ for another edge $e' \in E''$ and $e'$ charges $\varDelta _1$, then e charges $\varDelta _2$, otherwise it charges $\varDelta _1$.

We claim that each face of H receives at most one unit of charge. Let $\varDelta =\varDelta {abc}$ be a face in H. Note that if $\varDelta$ receives positive charge from an edge $e\in E''$, then an end portion of e lies in $\varDelta$, and does not use any gap in the interior of $\varDelta$. Consequently if $\varDelta$ received positive charge from edges $e_1,e_2\in E''$, then the end portions of $e_1$ and $e_2$ in $\varDelta$ cannot cross, and they are incident to the same vertex of $\varDelta$. Therefore, all edges in $E''$ that charge $\varDelta$ are incident to the same vertex of $\varDelta$, say a, and cross the edge of $\varDelta$ opposite to a, namely (b, c). Let $\varDelta '=\varDelta 'bcd$ be the face of the plane graph H on the opposite side of (b, c).

The gap of edge (b, c) can be used for at most one crossing along (b, c). If the gap of (b, c) is used for a crossing with one of the end portions in $\varDelta$, then e sends 1 unit charge to $\varDelta$. The only other edge that could possibly send a charge to $\varDelta$ is the edge $(a,d) \in E''$ that uses its own gap to cross (b, c). However, in this case, (a, d) charges one unit to $\varDelta '$ in our charging scheme. If the gap of (b, c) is not used for any of these end portions in $\varDelta$, then the edge (a, d) may send 1 unit charge to $\varDelta$. Overall, $\varDelta$ receives at most 1 unit of charge. Consequently, $|E''|$ is bounded above by the number of faces of H, which is $2n-4$, as required.   $\square$

We now show that the bound of Theorem 2 is worst-case optimal. A 2-planar graph with n vertices and $5n-10$ edges is also $1$-gap-planar (see Lemma 6). Pach and Tóth [38] construct such a graph by starting with a plane graph with pentagonal faces (e.g., using nested copies of an icosahedron), and then add all five diagonals in each pentagonal face; see Fig. 2(a). This construction yields a $1$-gap-planar graph with n vertices and $m=5n-10$ edges for all $n\ge 20$, $n\equiv 5 \pmod {15}$.

Fig. 2.

Patterns that produce $1$-gap-planar graphs with n vertices and $5n-\varTheta (1)$ edges.

We can modify this construction by inserting a new vertex in one or more pentagons, and connecting it to the 5 vertices of the pentagon; see Fig. 2(b). Every new edge crosses exactly one diagonal of the pentagon, so the new crossings can be charged to the new edges. Since every new vertex has degree 5, the equation $m=5n-10$ prevails. By inserting a suitable number of vertices into pentagons, we obtain constructions for $n\in \mathbb {N}$ such that $20\le n\le 32$ or $n\ge 38$. A similar construction is based on hexagonal faces; see Fig. 2(c). Start with a fullerene, that is, a 3-regular, plane graph $G_0$ with $n_0$ vertices, 12 pentagon faces, and $n_0/2-10$ hexagon faces (including the external face). Add diagonals in each face to connect a vertex to their second neighbors (the graph is 2-planar so far); finally insert a new vertex in each face of $G_0$, and connect them to all vertices of that face. We obtain a $1$-gap-planar graph G. The number of vertices is $n=n_0+12+(n_0/2-10)=\frac{3}{2}n_0+2$, and the number of edges is $m=\frac{3}{2}n_0+10\cdot 12+ 12\cdot (n_0/2-10)= \frac{15}{2}n_0= 5n-10$. Fullerenes exist for $n_0=20$ and for all even integers $n_0\ge 24$ [14]. This yields a lower bound of $5n-10$ for $n=32$ and for all $n\ge 35$ where $n\equiv 2\mod 3$. However, similarly to the previous construction, the equation $m=5n-10$ prevails if we delete up to 12 vertices inserted into pentagons. Consequently, the upper bound $5n-10$ in Theorem 2 is tight for all $n\ge 20$.

Theorem 3

For every $n \ge 20$ there exists a $1$-gap-planar graph G with n vertices and $5n-10$ edges.

4 $1$-gap-planar Drawings of Complete Graphs

Theorem 4

The complete graph $K_n$ is $1$-gap-planar if and only if $n \le 8$.

Proof

Figure 3(a) shows a $1$-gap-planar drawing of $K_8$, and by monotonicity the graphs $K_1,\ldots ,K_7$ are $1$-gap-planar as well. We now prove that $K_9$ is not $1$-gap-planar, which again by monotonicity settles all cases $K_n$ for $n \ge 9$.

Since $K_9$ has 36 edges and $\mathrm{cr}(K_9) = 36$, a $1$-gap-planar drawing of $K_9$ can only arise from assigning exactly one gap to each edge in a crossing-minimal drawing of $K_9$ (cf. Property 1). We obtain a contradiction by showing that in every crossing-minimal drawing of $K_9$ some edge has no crossing at all.

Let $\varGamma ^*$ be the planarization of such a crossing-minimal drawing $\varGamma$. Note that $\varGamma ^*$ has $n^*=45$ vertices and $m^*=108$ edges (since it has 9 real vertices of degree 8 and 36 dummy vertices of degree 4), so by Euler’s formula, the number of faces of $\varGamma ^*$ is $f^* = m^* - n^* + 2 = 108 - 45 + 2 = 65$. For a real vertex u of $\varGamma ^*$, we denote by F(u) the set of faces of $\varGamma ^*$ that are incident to u. We claim that $\varGamma ^*$ is biconnected and $|F(u)|=8$ for every real vertex u of $\varGamma ^*$.

Suppose, for a contradiction, that $\varGamma ^*$ is not biconnected. Then it contains a cut-vertex c, which is either a dummy or a real vertex. If c is a dummy vertex, note that it is adjacent to exactly two connected components of $\varGamma ^* \setminus \{c\}$. Then we can reflect the drawing of one of the two components, thereby eliminating the crossing at c, which contradicts the crossing-minimality of $\varGamma$. We now show that no real vertex is a cut-vertex in $\varGamma ^*$. Every 3-cycle in $K_9$ forms a simple cycle in $\varGamma ^*$ (since $\varGamma$ is a simple drawing and thus adjacent edges do not cross). On the other hand, any three real vertices in $\varGamma ^*$ are part of a 3-cycle in $K_9$, and thus part of a simple cycle in $\varGamma ^*$. Hence, no real vertex is a cut-vertex in $\varGamma ^*$. Finally, $|F(u)|=8$ because every real vertex u has degree 8 and $\varGamma ^*$ is biconnected.

It follows that there are real vertices u, v which share a face (i.e. $F(u)\,\cap \,F(v) \not = \emptyset$), as otherwise there would have to be $\sum _u |F(u)| = 9\cdot 8 = 72 > 65 = f^*$ faces. But now the edge (u, v) can be redrawn inside this face, and since $\varGamma$ was assumed to be crossing-minimal this edge can not have had any crossing to begin with.    $\square$

Fig. 3.

A $1$-gap-planar drawing of (a) $K_8$ and (b) $K_{3,12}$.

5 Recognizing $1$-gap-planar Graphs

We use 1GapPlanarity to denote the problem of deciding whether a given graph G is $1$-gap-planar. We show that 1GapPlanarity is NP-complete, and we use a reduction from 3Partition. Recall that an instance of 3Partition consists of a multiset $A=\{a_1,a_2,\ldots ,a_{3m}\}$ of 3m positive integers in the range (B / 4, B / 2), where B is an integer such that $B=1/m \cdot \sum ^{3m}_{i=1}a_i$, and asks whether A can be partitioned into m subsets $A_1,A_2,\ldots ,A_m$, each of cardinality 3, such that the sum of integers in each subset is B. This problem is strongly NP-hard [24], and thus we may assume that B is bounded by a polynomial in m.

The fact that 1GapPlanarity is in NP can easily be shown by exploiting Property 2.

Our reduction is reminiscent to the reduction used in [9]. However, the proof in [9] holds only for the case in which a clockwise order of the edges around each vertex is part of the input, i.e., only if the rotation system of the input graph is fixed. A similar reduction is also used in [10], in which the rotation system assumption is not used. However, the gadgets used in [10] have a unique embedding. We do not use the fixed rotation system assumption, nor we can easily derive a unique embedding for our gadgets, and thus have to deal with additional challenges in our proof. In what follows we define a “blob” graph that will be used to enforce an ordering among the edges adjacent to certain vertices. Consider the complete bipartite graph $K_{3,12}$, whose crossing number is 30 [33, 41]. We exhibit a $1$-gap-planar drawing of $K_{3,12}$ with exactly 30 gaps in Fig. 3(b). Note that two degree-12 vertices, u and v, are drawn on the outer face. Since $K_{3,12}$ has 36 edges, the next lemma easily follows.

Lemma 2

Every $1$-gap-planar drawing of $K_{3,12}$ has at most 6 gap-free edges.

A blob B is a copy of $K_{3,12}$. A gapped chain $\mathcal C$ of a $1$-gap-planar drawing is a closed, possibly nonsimple, curve such that any point of $\mathcal C$ either belongs to a gap edge or it corresponds to a vertex.

Lemma 3

Let u and v be any two degree-12 vertices of B. Every $1$-gap-planar drawing $\varGamma$ of B contains a gapped chain $\mathcal C$ containing u and v.

Sketch of proof. Let $\varGamma ^*$ be the planarization of $\varGamma$. Let $\varGamma '$ be the subgraph of $\varGamma ^*$ consisting only of those edges that correspond to or belong to gap edges of $\varGamma$.

We prove that $\varGamma '$ contains two edge-disjoint paths from u to v. Note that these two edge-disjoint paths may meet at real vertices and at dummy vertices (i.e., a crossing between two gap edges). A curve that goes through these two paths is the desired gapped chain. According to Menger’s theorem, two such paths exist if and only if every (u, v)-cut of $\varGamma '$ has size at least 2, where a (u, v)-cut of $\varGamma '$ is a set of edges of $\varGamma '$ whose removal disconnects u and v. Such edge cuts correspond to cycles in the dual, which in turn correspond to curves that separate u and v by crossing a set of edges. By Lemma 2, one can show that any such curve crosses at least two gap edges in the original drawing $\varGamma$.   $\square$

We are now ready to show how to transform an instance A of 3Partition into an instance $G_A$ of 1GapPlanarity. We start by defining some gadgets for our construction. A path gadget $P_k$ is a graph obtained by merging a sequence of $k>0$ blobs as follows. Denote by $B_1$, $B_2$, $\dots$, $B_k$, k blobs such that $u_i$ and $v_i$ are two vertices of degree 12 in $B_i$. We let $v_i = u_{i+1}$ for $i=1,\dots ,k-1$, each of these vertices is an attaching vertex. Thus, $P_k$ has $k+1$ attaching vertices. A $1$-gap-planar drawing of $P_k$ is such that any two gapped chains of any two blobs $B_i$ and $B_j$ ($i<j$) do not share points, except at a possible common attaching vertex. A schematization of $P_k$ (for $k=3$) is shown in Fig. 4(a). A top beam $G_t$ is a path gadget $P_k$ with $k= 3m(\lceil B/2 \rceil +2)+1$. Recall that $G_t$ has $3m(\lceil B/2 \rceil +2)+2$ attaching vertices. A right wall $G_r$ is a path gadget $P_k$ with $k= 2$. Symmetrically, a bottom beam $G_r$ is a path gadget with $k= 3m(\lceil B/2 \rceil +2)+1$, and a left wall $G_l$ is a path gadget with $k=2$. A global ring R is obtained by merging $G_t$, $G_r$, $G_b$, and $G_l$ in a cycle as in Fig. 4(b). Again, in any $1$-gap-planar drawing $\varGamma _R$ of R, the gapped chains of any two blobs $B_i$ and $B_j$ do not share points, except at a possible common attaching vertex. Thus, $\varGamma _R$ contains a gapped chain $C_R$ that is the union of all the gapped chains of the blobs of R.

Fig. 4.

(a) Schematization of a path gadget $P_3$. (b) A global ring R. (c) Schematization of the instance $G_A$ with $m = 3$, $A = \{7, 7, 7, 8, 8, 8, 8, 9, 10\}$ and $B = 24$. Transversal paths are routed according to the following solution of 3Partition $A_1 = \{7, 7, 10\}$, $A_2 = \{7, 8, 9\}$ and $A_3 = \{8, 8, 8\}$. For simplicity, the gapped chains of the various blobs are not shown, as well as vertex w and all the degree-2 vertices of the transversal paths.

We start the construction of $G_A$ with a global ring R. Let $\alpha$, $\beta$, $\gamma$, $\delta$ be the attaching vertices shared by $G_l$ and $G_t$, $G_t$ and $G_r$, $G_r$ and $G_b$, $G_b$ and $G_l$, respectively (see also Fig. 4(b)). First we add the edges $(\alpha ,\beta )$ and $(\gamma ,\delta )$. Denote as $R^+$ the resulting graph, and consider a $1$-gap-planar drawing of this graph. The gapped chain of R subdivides the plane into a set of connected regions, such that only two of them contain all of $\alpha$, $\beta$, $\gamma$, and $\delta$ on their boundaries. We denote these two regions as $r_1$ and $r_2$. For ease of illustration, we assume that one of them is infinite (as in Fig. 4(b)), say $r_2$. Since the drawing is $1$-gap-planar, each of $(\alpha ,\beta )$ and $(\gamma ,\delta )$ is drawn entirely in one of these two regions. We assume that both these two edges are drawn in the same region, say $r_2$, and we will later show that this is the only possibility in any $1$-gap-planar drawing of the final graph $G_A$. We continue by connecting the top and bottom beams by a set of 3m columns; refer to Fig. 4(c). Each column consists of $2m - 1$ cells; a cell consists of a set of pairs of crossing edges, called its vertical pairs. In particular, there are $m-1$ bottom cells, one central cell and $m - 1$ top cells. Cells of the same column are separated by $2m - 2$ path gadgets, called floors. Note that we are assuming a particular left-to-right order for the attaching vertex of a floor, we will see that this is the only possible order in a $1$-gap-planar drawing. The central cells (we have 3m of them in total) have a number of vertical pairs depending on the elements of A. Specifically, the central cell $C_i$ of the i-th column contains $a_i$ vertical pairs connecting its delimiting floors ($i \in \{1, 2, \dots , 3m\}$). Each of the remaining cells each has $\lceil B/2 \rceil +1$ vertical pairs. Hence, a noncentral cell contains more edges than any central cell. Further, the number of attaching vertices of a floor can be computed based on how many vertical pairs must be connected to the gadget. It is now straightforward to see that it is not possible to draw both a column and one of $(\alpha ,\beta )$ and $(\gamma ,\delta )$ in $r_1$ or $r_2$ without violating $1$-gap-planarity. Hence, we shall assume that both $(\alpha ,\beta )$ and $(\gamma ,\delta )$ are in $r_2$ and that all the columns are in $r_1$. Consider now a $1$-gap-planar drawing of a column. If we invert the left-to-right order of the attaching vertices of a floor (i.e., we mirror its drawing), then the resulting drawing is not $1$-gap-planar, since each floor delimits at least one noncentral cell with $\lceil B/2 \rceil +1$ vertical pairs. Moreover, since each vertical pair has a gap edge, two vertical pairs cannot cross each other in a $1$-gap-planar drawing, and thus the drawings of the columns are disjoint one another. Finally, let a and b be the attaching vertices of the left and right walls distinct from $\alpha$, $\beta$, $\gamma$, and $\delta$. We connect a and b with m pairwise internally disjoint paths, called transversal paths; each transversal path has exactly $(3m - 3)(\lceil B/2 \rceil +1) + B$ edges. The routing of these paths will be used to determine a solution of A, if it exists. Thus, we aim at forcing the transversal paths to be inside $r_1$ in a $1$-gap-planar drawing of the graph. For this purpose, adding a vertex w connected to all the attaching vertices of $G_t$ and $G_b$ will suffice. Due to the presence of the columns in $r_1$, vertex w must be in $r_2$ and, due to the edges $(\alpha ,\beta )$ and $(\delta ,\gamma )$ in $r_2$, all its incident edges (except at most two) are gapped. Thus, the transversal paths must be drawn in $r_1$. This concludes the construction of $G_A$.

We can prove the following.

Theorem 5

The 1GapPlanarity problem is NP-complete.

We conclude by observing that our proof can be easily adjusted for the setting in which the rotation system of the input graph is fixed. We call this problem 1GapPlanarityWithRotSys. It suffices to choose a rotation system for $G_A$ that guarantees the existence of a $1$-gap-planar drawing ignoring the transversal paths (we already discussed the details of this drawing), and such that the transversal paths are attached to a and b with the ordering of their edges around a reversed with respect to the ordering around b. The membership of the problem to NP can be easily verified. Thus, the next theorem follows.

Theorem 6

The 1GapPlanarityWithRotSys problem is NP-complete.

6 Relationship Between $k$-gap-planar Graphs and Other Families of Beyond Planar Graphs

In this section we prove the following theorem.

Theorem 7

For every integer $k \ge 1$, the following relationships hold.

$$ (2k)\text{-planar } \subsetneq k\text{-gap-planar } \subsetneq (2k+2)\text{-quasiplanar }$$

We begin by showing the following.

Lemma 4

For all $k \ge 1$, every $k$-gap-planar drawing is $(2k+2)$-quasiplanar.

Proof

Recall that a graph G is q-quasiplanar, for $q\in \mathbb {N}$, if it admits a drawing in which there is no subset of q pairwise crossing edges, or equivalently if every subset of q edges has less than ${q\atopwithdelims ()2}=q(q-1)/2$ crossings. On the other hand, in a $k$-gap-planar drawing there are at most kq crossings among any q edges (Property 1). Consequently, a $k$-gap-planar graph is $(2k+2)$-quasiplanar.   $\square$

We also need to show that for every $k\in \mathbb {N}$ there is a $(2k+2)$-quasiplanar graph that is not $k$-gap-planar. We prove a stronger statement:

Lemma 5

For all $k \ge 1$, there is a 3-quasiplanar graph $G_k$ that is not $k$-gap-planar.

Proof

Let $k\in \mathbb {N}$. We construct a graph $G_k=(V,E)$ as follows. Start with $K_{3,3}$ and replace each edge by $t=19k$ edge-disjoint paths of length 2. Note that the total number of edges is $|E|=9\cdot 2t=18t$. Graph $G_k$ is 3-quasiplanar. Since $\mathrm{cr}(K_{3,3})=1$, it admits a drawing with precisely one crossing. The paths of length 2 can be drawn close to the edges of $K_{3,3}$ such that two paths cross if and only if the two corresponding edges of $K_{3,3}$ cross. Consequently any two crossing edges in this drawing are part of two paths that correspond to two crossing edges of $K_{3,3}$, which in turn implies that no three edges of $G_k$ pairwise cross.

Suppose that $G_k$ admits a $k$-gap-planar drawing $\varGamma$. Then the total number of crossings is at most $k|E|=18kt$. We derive a contradiction by showing that $\mathrm{cr}(G_k)\ge 19kt$. If we choose one of the t paths for each of the 9 edges of $K_{3,3}$ independently, then we obtain a subdivision of $K_{3,3}$, therefore there is a crossing between at least one pair of paths. There are $t^9$ ways to choose a path for each of the 9 edges of $K_{3,3}$. Each crossing between two paths in $\varGamma$ is counted $t^{9-2}=t^7$ times. Consequently, the total number of crossings in $\varGamma$ is at least $t^2=19kt$.   $\square$

We now show that every 2k-planar drawing is $k$-gap-planar. We note that a similar result can be also derived from [16] (Lemma 10) for the case $k=1$. A bipartite graph with vertex sets A and B is denoted as $H=(A,B,E)$. A matching from A into B is a set $M \subseteq E$ such that every vertex in A is incident to exactly one edge in M and every vertex in B is incident to at most one edge in M. The neighborhood of a subset $A' \subseteq A$ is the set of all vertices in B that are adjacent to a vertex in $A'$, and is denoted as $N(A')$. We recall that, by Hall’s theorem, the graph H has a matching from A into B if and only if for each set $A' \subseteq A$ it is $|N(A')| \ge |A'|$.

Lemma 6

For all $k \ge 1$, every (2k)-planar drawing is $k$-gap-planar.

Proof

Let G be a (2k)-planar graph, for any $k \ge 1$, and let $\varGamma$ be a 2k-planar drawing of G. Let $H = (A \cup B,E_H)$ be a bipartite graph obtained as follows. The set A has a vertex $a_{e,f}$ for each crossing in $\varGamma$ between two edges e and f of G. For each edge e of G there are k vertices $b^1_e,\dots ,b^{k}_e$ in B. For every pair of edges e, f of G that cross in $\varGamma$, graph H contains edges $(a_{e,f},b^1_e),\dots ,(a_{e,f},b^{k}_e)$ and $(a_{e,f},b^1_{f}),\dots ,(a_{e,f},b^{k}_{f})$ in H. Notice that if H admits a matching of A in B, then each crossing of $\varGamma$ between an edge e and an edge f of G can be assigned to either e or f, and no edge of G is assigned with more than k crossings.

Consider any subset $A'$ of A, and let $B' = N(A')$ be the neighborhood of $A'$ in B. We claim that $|A'| \le |B'|$. Let $E' \subseteq E_H$ denote the edges between $A'$ and $B'$. By construction every vertex in A has degree 2k, and hence $|E'| \ge 2k |A'|$. On the other hand, every vertex in B has degree at most 2k as every edge of G has at most 2k crossings, and hence $|E'| \le 2k |B'|$. Hence $|A'| \le |B'|$ as claimed.

By Hall’s theorem, it now follows that H admits a matching from A into B, which corresponds to an assignment of gaps in $\varGamma$ such that no edge has more than k gaps, i.e., $\varGamma$ is a $k$-gap-planar drawing.   $\square$

To conclude the proof of Theorem 7, we should prove that for every $k \ge 1$, there is a $k$-gap-planar graph that is not 2k-planar. A stronger result holds:

Lemma 7

For every $k \ge 1$, there exists a $1$-gap-planar graph $G_k$ that is not k-planar.

7 Conclusions and Open Problems

We introduced $k$-gap-planar graphs, our results give rise to several questions for future research. Among them are: (i) We proved that $k$-gap-planar graphs have $O(\sqrt{k} \cdot n)$ edges, and that $1$-gap-planar graphs have at most $5n-10$ edges, which is a tight bound. Can we establish a tight bound also for $2$-gap-planar graphs? (ii) We proved that $K_n$ is $1$-gap-planar if and only if $n \le 8$. A similar characterization could be studied also for complete bipartite graphs. Note that $K_{5,7}$ is not $1$-gap-planar since it has crossing number greater than its number of edges, while we can exhibit a $1$-gap-planar drawing of $K_{5,6}$. It is open whether $K_{6,6}$ is $1$-gap-planar. Similarly, $K_{3,12}$ (Fig. 3(b)) and $K_{4,8}$ are $1$-gap-planar, while we ask if this is true also for $K_{3,13}$ and $K_{4,9}$. (iii) We proved that deciding whether a graph is $1$-gap-planar is NP-complete, even if the rotation system is fixed. Does the problem become polynomial for drawings in which all vertices are on the outer boundary? (iv) We proved that a drawing with at most 2k crossings per edge is $k$-gap-planar, and that a $k$-gap-planar drawing does not contain $2k+2$ pairwise crossing edges. Do $1$-gap-planar graphs have RAC drawings with at most 1 or 2 bends per edge?