Structural Parameterizations of $𝒌$-Planarity

Since the edges in $G$ can cross other edges $km$ times in total, for each $u\in X$, there is a spoke between $r$ and $u$ that does not cross any edges of $G$. Let $P_u$ be such a spoke for each $u\in X$ and $𝒫≔\{P_u\mid u\in X\}$. Although spokes in $𝒫$ may cross, we can untangle them, preserving the subdrawing for $G$. Then we redraw the other spokes along $𝒫$. $◀$

We will use this lemma in the following form.

By Lemma 2, $G^{\prime \prime }$ has a $k$-planar drawing ${\mathrm{\Gamma }}^{\prime }$ in which all the spokes incident to $s^{\prime }$ have no crossings. Let $\mathrm{\Gamma }$ be the subdrawing of ${\mathrm{\Gamma }}^{\prime }$ induced by $G^{\prime }$. As shown in the proof of Lemma 2, for each $u\in S$, there is a spoke $P_u$ between $s$ and $u$ that has no crossing with any edge of $G$ in $\mathrm{\Gamma }$. Since this spoke $P_u$ does not cross any spoke incident to $s^{\prime }$, the uncrossing operation and redrawing spokes between $s$ and $u$ used in Lemma 2 never create a new crossing with spokes incident to $s^{\prime }$. Thus, by applying Lemma 2 to $G^{\prime }$ and $\mathrm{\Gamma }$, we have a $k$-planar drawing of $G^{\prime \prime }$ being claimed. $◀$

We now turn to our reduction from Two-Sided $k$-Planarity, in which we are given a bipartite graph $G=(X\cup Y,E)$ with two independent sets $X$ and $Y$, and an integer $k$. The goal is to determine whether $G$ has a 2-layer $k$-planar drawing, which is a special case of a $k$-planar drawing in which the vertices in $X$ are drawn on a line, the vertices in $Y$ are drawn on another line parallel to the first line, and each edge is drawn as a straight line.

The idea of our reduction is the same as that of Garey and Johnson [15] from Bipartite Crossing Number to Crossing Number. We remark that, however, the proof is more involved due to the difficulty of $k$-planarity.

Let $⟨G=(X,Y,E),k⟩$ be an instance of Two-Sided $k$-Planarity, where $n_X=|X|$, $n_Y=|Y|$, and $m=|E|$. We construct a graph $G^{\prime }$ from $G$ as follows (see Figure 2):

1. 1.

   we introduce two vertices $u_X,u_Y$;

2. 2.

   for each $x\in X$, add ${\mathrm{\ell }}_1≔km+1$ spokes between $u_X$ and $x$;

3. 3.

   for each $y\in Y\cup \{u_X\}$, add ${\mathrm{\ell }}_2≔k({\mathrm{\ell }}_1{n}_X+m)+1$ spokes between $u_Y$ and $y$.

Then, $⟨G^{\prime },k⟩$ is the instance we construct for $k$-Planarity Testing. It is easy to verify that the above construction can be done in polynomial time.

It is clear that we can obtain a $k$-planar drawing of $G^{\prime }$ from a 2-layer $k$-planar drawing of $G$ by drawing $u_X$, $u_Y$, and spokes as Figure 2. Hence, we only show the other direction.

Suppose that the graph $G^{\prime }$ admits a $k$-planar drawing ${\mathrm{\Gamma }}^{\prime }$. By Corollary 3, we can assume that all the spokes in $G^{\prime }$ have no crossings in ${\mathrm{\Gamma }}^{\prime }$. We then replace the set of spokes connecting two vertices with a single edge between them and contract the edge between $u_X$ and $u_Y$ by identifying them into a new vertex $u$ in ${\mathrm{\Gamma }}^{\prime }$. We let $G^{\ast }$ denote the graph obtained in this way. As all spokes have no crossings, the obtained drawing of $G^{\ast }$, denoted by ${\mathrm{\Gamma }}^{\ast }$, is still $k$-planar. Let us note that $G^{\ast }$ is isomorphic to the graph obtained from $G$ by adding a universal vertex $u$ (which is a vertex adjacent to all the vertices in $G$). We claim that we can draw a closed curve $C$ passing through all the vertices in $V(G^{\ast })\setminus \{u\}$ such that

1. 1.

   no edge of $G^{\ast }$ intersects $C$ (i.e., $C$ is a noose in ${\mathrm{\Gamma }}^{\ast }$);

2. 2.

   all the edges incident to $u$ are contained in one of the two regions $R$ with boundary $C$;

3. 3.

   all the edges in $E(G)$ are contained in the other region with boundary $C$;

4. 4.

   all the vertices in $X$ appear consecutively on $C$;

5. 5.

   all the vertices in $Y$ appear consecutively on $C$.

To this end, we draw a curve $C$ while keeping track of the cyclic ordering of the edges incident to $u$ (and hence the neighbors of $u$) in ${\mathrm{\Gamma }}^{\ast }$. As these incident edges have no crossings, we can draw such a curve satisfying (1), (2), and (3). To see the properties (4) and (5), suppose for contradiction that there are $x,x^{\prime }\in X$ and $y,y^{\prime }\in Y$ such that $x,y,x^{\prime },y^{\prime }$ appear in this order on $C$. Due to the property (2), $C$ can be seen as a closed curve on ${\mathrm{\Gamma }}^{\prime }$ such that the region corresponding to $R$ contains all spokes of $G^{\prime }$. Let $P_x$ be a path in $G^{\prime }$ between $x$ and $x^{\prime }$ via $u_X$ consisting only of spokes. We define $P_y$ similarly. In ${\mathrm{\Gamma }}^{\prime }$ those paths are contained in $R$ and $C$. However, since the vertices $x,x^{\prime },y,y^{\prime }$ are all placed on $C$, such a drawing must yield a crossing, which contradicts the fact that spokes in $G^{\prime }$ have no crossings in ${\mathrm{\Gamma }}^{\prime }$.

Let $X=\{x_1,\mathrm{\dots },x_{n_X}\}$ and let $Y=\{y_1,\mathrm{\dots },y_{n_Y}\}$ such that $x_1,\mathrm{\dots },x_{n_X},y_1,\mathrm{\dots },y_{n_Y}$ appear on $C$ in this order. We now convert the drawing ${\mathrm{\Gamma }}^{\ast }$ into a drawing $\widehat{\mathrm{\Gamma }}$ such that

• $\mathrm{■}$

  all the vertices in $V(G^{\ast })\setminus \{u\}$ are placed on a line $\mathrm{\ell }$ in the order $x_1,\mathrm{\dots },x_{n_X},y_1,\mathrm{\dots },y_{n_Y}$;

• $\mathrm{■}$

  all the edges incident to $u$ are drawn as straight segments in a half plane separated by $\mathrm{\ell }$;

• $\mathrm{■}$

  all the other edges are drawn in the other half plane in such a way that the curve corresponding to an edge forms a semicircular arc between the endpoints.

See Figure 3(a) for an illustration.

Observe that this drawing $\widehat{\mathrm{\Gamma }}$ is also $k$-planar as two edges of $G^{\ast }$ cross in $\widehat{\mathrm{\Gamma }}$ only if they cross in ${\mathrm{\Gamma }}^{\ast }$ as well. Moreover, $\widehat{\mathrm{\Gamma }}$ is simple, meaning that no pair of edges crosses more than once and no two edges incident to a common vertex cross. This in turn can be converted into a $k$-planar drawing $\mathrm{\Gamma }$ as in Figure 3(b). The subdrawing of $\mathrm{\Gamma }$ induced by $G^{\ast }-\{u\}$ is a $2$-layer $k$-planar drawing such that two edges in $G^{\ast }-\{u\}$ cross if and only if they cross in $\widehat{\mathrm{\Gamma }}$. Hence, $G$ ($=G^{\ast }-\{u\}$) admits a 2-layer $k$-planar drawing. $◀$

This reduction immediately gives us the following consequence. Note that Theorem 5 is optimal in the sense that every graph with feedback vertex set number $1$ is planar.

The NP-membership of $1$-Planarity Testing is shown in [26]. It is known that Two-Sided $k$-Planarity is NP-complete even on trees [25, Theorem 11]. Thus, the graph $G^{\prime }$ constructed in the proof of Lemma 4 has feedback vertex set number at most 2. This in turn implies the claim by Lemma 1. $◀$

The above reduction leads to further consequences. To see this, we first sketch the reduction used in [25, Theorem 11]. They performed a polynomial-time reduction from Bandwidth to Two-Sided $k$-Planarity. Let $T$ be a tree, $b$ be a positive integer, and $\mathrm{\ell }$ be an arbitrary even number with $\mathrm{\ell }\ge 2b^2$. For each edge in $T$, each edge $e\in E(T)$ is subdivided once by introducing a new vertex $w_e$, and we add $\mathrm{\ell }$ leaves adjacent to each original vertex in $T$. They showed that there is an ordering $v_1,\mathrm{\dots },v_{|V(T)|}$ of $V(T)$ such that $|i-j|\le b$ for any edge $\{v_i,v_j\}\in E(T)$ if and only if the obtained graph $T^{\prime }$ has a 2-layer $k$-planar drawing with $k=(\mathrm{\ell }+4)(b-1)/2$.

It is known that the problem Bandwidth is W[1]-hard with respect to treedepth, even on trees [16]. The above reduction we sketched [25, Theorem 11] also preserves the boundedness of treedepth. To see this, we convert an elimination forest $F^{\ast }$ of $T$ to that of $T^{\prime }$ as follows. Starting from $F^{\ast }$, we add the $\mathrm{\ell }$ leaves attached to each vertex as leaf children of it. For each edge $e\in E(T)$, one of the end vertices, say $v$, is a descendant of the other in $F^{\ast }$. We then add $w_e$ as a leaf child of $v$ in $F^{\ast }$. It is easy to verify that the rooted forest obtained in this way is an elimination forest of $T^{\prime }$ and its height increases by at most 1 compared to the original elimination forest of $T$, yielding that $\mathrm{td}(T^{\prime })\le \mathrm{td}(T)+1$. Hence, Two-Sided $k$-Planarity is also W[1]-hard with respect to treedepth, even on trees. Moreover, the reduction used in Lemma 4 increases the treedepth by at most $3$, which implies the claim. $◀$

For any constant $c\ge 1$, it is NP-hard to distinguish the following cases: the bandwidth of $T$ is at most $b$ or more than $cb$ for a given tree $T$ and an integer $b$ [10]. We set $\mathrm{\ell }=2t-4$ for sufficiently large $t$ and construct a tree $T^{\prime }$ according to the above reduction from $T$. If the bandwidth of $T$ is at most $b$, then we have $\mathrm{lcr}(T^{\prime })\le t(b-1)$. Otherwise, we have $\mathrm{lcr}(T^{\prime })\ge tcb$. This implies that a polynomial-time $c$-approximation algorithm for Two-Sided $k$-Planarity on trees distinguishes the above two cases. $◀$

Combining Lemma 4 and Lemma 7, we obtain the following.

Let $⟨S=\{x_1,\mathrm{\dots },x_{|S|}\},B,b⟩$ be an instance of Unary Bin Packing. In the following, we assume that $b\ge 3$. We construct an instance $⟨G=(V,E)⟩$ of $1$-Planarity Testing as follows. Let $G$ be a graph consisting of vertices $u_1,u_2,v_1,\mathrm{\dots },v_b$, and paths $P_1,\mathrm{\dots },P_{|S|}$ with $|V(P_i)|=x_i$ for $1\le i\le |S|$. Let $𝒫=\{P_1,\mathrm{\dots },P_{|S|}\}$. We add a path of length $B$ between $v_i$ and $v_{i+1}$ for each $1\le i\le b$, where $v_{b+1}≔v_1$. These paths form a cycle $C$ of $bB$ vertices, passing through $v_i$ for all $i$. Next, we add an edge between $u_i$ and each vertex in $P_j$ for $1\le i\le 2$ and $1\le j\le |S|$. Let $m$ be the number of edges in the graph constructed so far (namely, $m=4bB-|S|$). Finally, for $1\le i\le b$, we add ${\mathrm{\ell }}_1≔m+1$ spokes between $u_1$ and $v_i$ and add ${\mathrm{\ell }}_2≔({\mathrm{\ell }}_{1}b+m)+1$ spokes between $u_2$ and $v_i$. See Figure 4 for an illustration of the constructed graph $G$. Observe that, by construction, removing $b+2$ vertices, say $u_1,u_2,v_1,\mathrm{\dots },v_b$, yields a path forest. The construction can be done in polynomial time.

From a solution of Unary Bin Packing, we can obtain a $1$-planar drawing of $G$ easily, as in Figure 5.

To be more precise, let $\{S_1,\mathrm{\dots },S_b\}$ be a solution for Unary Bin Packing. We first draw the cycle $C$ as a circle in such a way that the spokes between $u_1$ and $v_i$ partition the interior of the circle into $b$ regions $R_1,\mathrm{\dots },R_b$, where $R_i$ is enclosed by a spoke between $u_1$ and $v_i$, a spoke between $u_1$ and $v_{i+1}$, and a path between $v_i$ and $v_{i+1}$ on $C$. For each region $R_i$, we draw a path $P_j\in 𝒫$ inside $R_i$ if $x_j\in S_i$. Since the sum of the numbers of vertices of the paths drawn in $R_j$ is exactly $B$, we can draw those paths so that each edge in the path between $v_i$ and $v_{i+1}$ is crossed exactly once. Hence, we can draw $G$ so that each edge is crossed at most once.

For the other direction, suppose that $G$ has a 1-planar drawing. By Corollary 3, there exists a 1-planar drawing $\mathrm{\Gamma }$ of the graph $G$ such that all the spokes in $G$ have no crossings. Since the spokes have no crossings in $\mathrm{\Gamma }$, the subdrawing induced by them is planar, and hence there are two vertices $v_i$ and $v_j$ that belong to the outer cycle of this subdrawing. As $b\ge 3$, all the other $v_{\mathrm{\ell }}$’s are drawn inside the region bounded by this outer cycle. Moreover, since two consecutive $v_{\mathrm{\ell }}$ and $v_{\mathrm{\ell }+1}$ are connected by a path in $C$, the two distinguished vertices $v_i$ and $v_j$ must be consecutive, namely $j=(i+1)modb$. By appropriately renaming those vertices, we can assume that $G-{\bigcup }_{1\le i\le |S|}V(P_i)$ are drawn as in Figure 6(a). Then, there are $b$ internally vertex-disjoint paths $Q_1,\mathrm{\dots },Q_b$ between $u_1$ and $u_2$ such that $Q_i$ is a concatenation of spokes between $u_1$ and $v_i$ and between $v_i$ and $u_2$ for each $i$. These paths separate the plane into $b$ regions, $R_1,\mathrm{\dots },R_b$ as Figure 6(b).

As each path $P_i$ cannot lie in two different regions, $𝒫$ can be partitioned into $\{{𝒫}_1,\mathrm{\dots },{𝒫}_b\}$, where ${𝒫}_i\subseteq 𝒫$ is the collection of paths drawn inside $R_i$. Observe that, for each path $P_j\in {𝒫}_i$, there are $x_i=|V(P_i)|$ edge-disjoint paths between $u_1$ and $u_2$ that are drawn inside $R_i$. Each of them must cross the path between $v_i$ and $v_{i+1}$ on $C$, implying that there are at most $B$ such paths inside $R_i$ as $\mathrm{\Gamma }$ is 1-planar. Since there are exactly $b$ regions, each ${𝒫}_i$ must satisfy ${\sum }_{P\in {𝒫}_i}|V(P)|=B$. Therefore, we can partition $S$ into $b$ sets such that the sum of each set is exactly $B$. $◀$

Observe that the above reduction still works even if we add an edge between $u_1$ and each vertex in $C$, in which case the vertex set $\{u_1,u_2\}$ forms a dominating set.

As mentioned in Section 1, Cabello and Mohar [4] showed that $1$-Planarity Testing is NP-hard even on near-planar graphs. Theorem 9 strengthens their hardness result as the graph $G$ constructed in the reduction is a near-planar graph with the following properties.

We add $2bB$ copies of $B+1$ to $S$ of an instance of Unary Bin Packing and increase the capacity of a bin by $2B(B+1)$ to obtain an instance with the claimed condition. We can show that there is no other solution than to distribute those $B+1$’s evenly to $b$ bins, making it equivalent to the original instance. $◀$

The reduction is almost analogous to the one used in Theorem 9. Let $I=⟨S,B,b⟩$ be an instance of Unary Bin Packing. We can assume that $b\ge 3$ and $x\le \sqrt{B}-1$ for all $x\in S$ due to Lemma 12. While the basic construction of the graph $G$ is the same as in Theorem 9, it differs in the following points:

• $\mathrm{■}$

  the cycle $C$ contains exactly $b$ vertices $v_1,\mathrm{\dots },v_b$;

• $\mathrm{■}$

  for each $x_i\in S$, $G$ contains a clique $C_i$ with $x_i$ vertices, instead of a path $P_i$, such that each vertex in the clique is adjacent to both $u_1$ and $u_2$;

• $\mathrm{■}$

  for each $v_i$, we add ${\mathrm{\ell }}_1≔Bm+1$ spokes between $u_1$ and $v_i$ and add ${\mathrm{\ell }}_2≔B(b{\mathrm{\ell }}_1+m)+1$ spokes between $u_2$ and $v_2$, where $m$ is the number of edges in $G$ that are not contained in the spokes.

When we draw $G$ as in Figure 5, edges incident to a vertex in clique $C_i$ may have crossings. Each edge $e$ in $C_i$ may cross other edges in $C_i$ and all the edges between $u_j$ and a vertex in $C_i$ for $1\le j\le 2$. This implies that the number of crossings that $e$ involves is at most

Similarly, we can conclude that each edge between $u_j$ and a vertex in $C_i$ has at most $B-1$ crossings. Since we can assume that all the spokes in $G$ have no crossings due to Corollary 3, these spokes define exactly $b$ regions, each of which contains exactly $B$ vertices of cliques. Thus, we can show that $I$ is a yes-instance if and only if $G$ is $B$-planar as well.

As each connected component in $G-(V(C)\cup \{u_1,u_2\})$ consists of true twins, $G$ has a twin cover of size at most $b+2$. This completes the proof. $◀$

Let $G_S$ be a graph with $V(G_S)=S$ and $E(G_S)=\pi (I_{\ge 2})$. Let $G^{\prime }$ be the graph obtained from $G_S$ by subdividing each edge once. Then $G^{\prime }$ is a subgraph of $G$, and hence $G^{\prime }$ is $k$-planar. This implies that by Lemma 1, $G_S$ is $2k$-planar. Hence, ${\mathrm{\#}}_{\pi }(I_{\ge 2})=|E(G_S)|\le |S|\cdot 3.81\sqrt{2k}$, where the last inequality is shown in [1]. $◀$

It is known that, for a positive integer $k$, if $G$ contains $K_{7k+1,3}$ as a subgraph then $G$ is not $k$-planar [6, 32]. Hence, the following also immediately holds.

Next, we consider vertices of degree 2. The following lemma is a key ingredient of our kernelization. It is worth mentioning that, although a similar reduction rule is used in the case $k=1$ [2], the proof for the general case $k\ge 1$ is considerably more involved.

The ($\Rightarrow$) direction is clear. Suppose that $G^{\prime }≔G-\{u\}$ is $k$-planar and let $\mathrm{\Gamma }$ be a $k$-planar drawing of $G^{\prime }$. We can assume that $G^{\prime }$ has no vertex of degree 1.

Let $T_u=\{v\in V(G^{\prime })\setminus S\mid N_{G^{\prime }}(v)=\{s_1,s_2\}\}$. Then, we have $t_u=|T_u|\ge 16k^2|S|$. Let $𝒫$ be the set of paths between $s_1$ and $s_2$ via a vertex in $T_u$. Let us align the paths in $𝒫$ according to the cyclic order in $\mathrm{\Gamma }$ around $s_1$, as $P_0,P_1,\mathrm{\dots },P_{t_u-1}$. For two paths $P_i,P_j$, the cyclic difference of $P_i$ and $P_j$ is defined as $\min \{j-i,i-j+t_u\}$. We then claim the following.

Suppose that $P_i$ and $P_j$ do cross in $\mathrm{\Gamma }$. Let $c$ be a crossing point between $P_i$ and $P_j$, and let $C$ be a Jordan curve consisting of two arcs: the arc of $P_i$ from $s_1$ to $c$ and the arc of $P_j$ from $c$ to $s_1$. Such a crossing point $c$ can be chosen so that $C$ forms a closed curve. In both cases where $s_2$ is in the interior or in the exterior of regions bounded by $C$, from the condition that the cyclic difference of $P_i$ and $P_j$ is at least $4k$, there are at least $4k-1$ edges that must cross $C$ as shown in Figure 7. As $P_i,P_j$ can have at most $2k-1$ crossings other than $c$ each, and hence $4k-2$ crossings in total, this leads to a contradiction. $\mathrm{⊲}$

Let . As the cyclic difference of any pair of two paths in ${𝒫}^{\prime }$ is at least $4k$, by Claim 22, no two paths in ${𝒫}^{\prime }$ cross. We can also assume that each path in ${𝒫}^{\prime }$ does not cross itself, as it can be resolved as shown in Figure 8. Hence, they separate the plane into $4k|S|$ regions similarly to Figure 6(b). For each $0\le i\le 4k|S|$, let $R_i$ be the region that is bounded by two paths $P_{4ki}$ and $P_{4k(i+1)}$, where $P_{4k\cdot 4k|S|}≔P_0$. Observe that, for each vertex $v\in S\setminus \{s_1,s_2\}$, the number of paths in ${𝒫}^{\prime }$ crossed by an edge incident to $N_{G^{\prime }}(v)$ is at most $4k$: when $v$ belongs to region $R_i$, each edge incident to a vertex in $N_{G^{\prime }}(v)$ can only be in regions at most $2k$ apart from $R_i$, namely, $\{R_{jmod4k|S|}\mid i-2k\le j\le i+2k\}$. Since $S$ is a vertex cover of $G^{\prime }$, for every edge $e\in E(G^{\prime })$, $e=\{s_1,s_2\}$ (if it exists); $e$ is contained in a path in $𝒫$; or $e$ is incident to some vertex in $S\setminus \{s_1,s_2\}$ due to the assumption that there is no degree-1 vertex. Since at most $k$ paths in ${𝒫}^{\prime }$ can be crossed by $e=\{s_1,s_2\}$ (if it exists) and at most $4k(|S|-2)$ paths in ${𝒫}^{\prime }$ can be crossed by an edge incident to a vertex in $S\setminus \{s_1,s_2\}$, there are at least $4k|S|-(4k(|S|-2))-k=7k$ paths in ${𝒫}^{\prime }$ that are crossed only by the paths in $𝒫$ or not crossed at all.

Let $P\in {𝒫}^{\prime }$ be such a path. We remove all the paths in $𝒫$ but $P$ from $\mathrm{\Gamma }$. Observe that now $P$ has no crossings at all. Hence, we can redraw all the removed paths along $P$ without making a crossing. We can also add the path $(s_1,u,s_2)$ to $\mathrm{\Gamma }$ along $P$ in the same way and obtain a $k$-planar drawing of $G$. $◀$

By summarizing the above lemmas, we can obtain a kernelization algorithm.

We can obtain a similar result for the case of neighborhood diversity.

By plugging Lemma 24 to Theorem 23, we have the following.

Finally, we remark that the results of Theorem 23 and Corollary 25 cannot be generalized to vertex integrity and modular-width parameterizations (see [13, 16] for their definitions) unless $\mathrm{NP}\subseteq \mathrm{coNP}/\mathrm{poly}$, respectively. Let $G_1,\mathrm{\dots },G_t$ be graphs and $G$ be the disjoint union of $G_1,\mathrm{\dots },G_t$. Let $\mathrm{vi}(G)$ be the vertex integrity of $G$ and let $\mathrm{mw}(G)$ be the modular-width of $G$. Then, it holds that (1) $G$ is 1-planar if and only if $G_i$ is 1-planar for all $1\le i\le t$ and (2) $\mathrm{vi}(G)\le {\max }_i|V(G_i)|$ and $\mathrm{mw}(G)\le {\max }_i|V(G_i)|$. This implies that $1$-Planarity Testing parameterized by vertex integrity and by modular-width is AND-cross-compositional [3, 9, 12], implying that unless $\mathrm{NP}\subseteq \mathrm{coNP}/\mathrm{poly}$, there is no polynomial kernelization for $1$-Planarity Testing of size $\mathrm{poly}(\mathrm{vi}(G))$ or $\mathrm{poly}(\mathrm{mw}(G))$. As $\mathrm{td}(G)\le \mathrm{vi}(G)$, this kernelization lower bound also holds for treedepth parameterization.