11institutetext: Colgate University
11email<EMAIL_ADDRESS>22institutetext: University of Arizona
22email<EMAIL_ADDRESS>
# An FPT Algorithm for Bipartite Vertex Splitting

Reyan Ahmed 11 Stephen Kobourov 22 Myroslav Kryven 22

###### Abstract

Bipartite graphs model the relationship between two disjoint sets of objects.
They have a wide range of applications and are often visualized as 2-layered
drawings, where each set of objects is visualized as vertices (points) on one
of two parallel horizontal lines and the relationships are represented by
(usually straight-line) edges between the corresponding vertices. One of the
common objectives in such drawings is to minimize the number of crossings.
This, in general, is an NP-hard problem and may still result in drawings with
so many crossings that they affect the readability of the drawing. We consider
a recent approach to remove crossings in such visualizations by splitting
vertices, where the goal is to find the minimum number of vertices to be split
to obtain a planar drawing. We show that determining whether a planar
2-layered drawing exists after splitting at most $k$ vertices is fixed
parameter tractable in $k$.

###### Keywords:

fixed parameter tractability graph drawing vertex splitting

##  1 Introduction

Bipartite graphs are used in many applications to study complex systems and
their dynamics [20]. We can visualize a bipartite graph $G=(T\cup B,E)$ as a
2-layered drawing where vertices in $T$ are placed (at integer coordinates)
along the horizontal line defined by $y=1$ and vertices in $B$ along the line
below (at integer coordinates) defined by $y=0$.

A common optimization goal in graph drawing is to minimize the number of
crossings. Deciding whether a planar 2-layered drawing exists for a given
graph can be done in linear time, although most graphs, including sparse ones
such as cycles and binary trees, do not admit planar 2-layered drawings [6].
The problem of minimizing the number of crossings in 2-layered layouts is NP-
hard, even if the maximum degree of the graph is at most four [16], or if the
permutation of vertices is fixed on one of the layers [6]. The latter variant
of the problem is known as One-Sided Crossing Minimization (OSCM). The minimum
number of crossings in a 2-layered drawing can be approximated within a factor
of $1.47$ and $1.3+12/(\delta-4)$, where $\delta$ is the minimum degree, given
that $\delta>4$ [17]. Dujmović et al. [5] gave a fixed-parameter tractable
(FPT) algorithm with runtime $O(1.62^{k}\cdot n^{2})$, which was later
improved to $O(1.4656^{k}+kn^{2})$ [4]. Fernau et al. [10] reduced this
problem to weighted FAST (feedback arc sets in tournaments) obtaining a
subexponential time algorithm that runs in time
$2^{O(\sqrt{k}\log{k})}+n^{O(1)}$. Finally Kobayashi and Tamaki [14] gave a
straightforward dynamic programming algorithm on an interval graph associated
with each OSCM instance with runtime $2^{O(\sqrt{k}\log{k})}+n^{O(1)}$. They
also showed that the exponent $O(\sqrt{k})$ in their bound is asymptotically
optimal under the Exponential Time Hypothesis (ETH) [11], a well-known
complexity assumption which states that, for each $k\geq 3$, there is a
positive constant $c_{k}$ such that $k$-SAT cannot be solved in
$O(2^{c_{k}n})$ time where $n$ is the number of variables.

Minimizing the number of crossings in 2-layer drawings may still result in
visually complex drawings from a practical point of view [12]. Hence, we study
vertex splitting [7, 15, 8, 13] which aims to construct planar drawings, and
thus, avoid crossings altogether. In the split operation for a vertex $u$ we
delete $u$ from $G$, add two new copies $u_{1}$ and $u_{2}$, and distribute
the edges originally incident to $u$ between the two new vertices $u_{1}$ and
$u_{2}$. There are two main variations of the objective in vertex splitting:
minimizing the number of split operations (or splits) and minimizing the
number of split vertices (each vertex can be split arbitrary many times) to
obtain a planar drawing of $G$. Minimizing the number of splits is NP-hard
even for cubic graphs [9]. Nickel et al. [18] extend the investigation of the
problem and its complexity from abstract graphs to drawings of graphs where
splits are performed on an underlying drawing.

Vertex splitting in bipartite graphs with 2-layered drawings has not received
much attention [2]. In several applications, such as visualizing graphs
defined on anatomical structures and cell types in the human body [19], the
two vertex sets of $G$ play different roles and vertex splitting is allowed
only on one side of the layout. This has motivated the interest in splitting
the vertices in only one vertex partition of the bipartite graph. It has been
shown that minimizing splits in this setting is NP-hard for an arbitrary
bipartite graph [3].

The other variant – minimizing the number of split vertices – has been
recently considered and was shown to be NP-hard [1]. On the positive side, we
show that the problem is FPT parameterized by the natural parameter, that is,
the number of split vertices.

######  Problem (Crossing Removal with $\boldsymbol{k}$ Split Vertices –
CRSV($k$)).

Let $G=(T\cup B,E)$ be a bipartite graph. Decide whether there is a planar
2-layer drawing of $G$ after splitting at most $k$ vertices of $B$.

In the next section we prove the following theorem.

######  Theorem 1.1.

Given a bipartite graph $G=(T\cup B,E)$, the CRSV($k$) problem can be decided
in time $2^{O(k^{6})}\cdot m$, where $m$ is the number of edges of $G$.

We prove Theorem 1.1 using kernelization, one of the standard techniques for
designing FPT algorithms. The goal of kernelization is to reduce the input
instance to its computationally hard part on which a slower exact algorithm
can be applied. If the size of the reduced instance is bounded by a function
of the parameter, the problem can be solved by brute force on the reduced
instance yielding FPT runtime. Our reduction consists of two parts.

In the first part we identify and remove vertices that necessarily belong to
the solution (Step 1 below) and remove redundant vertices of the input graph
$G$; Step 2 below. Then we show that there is a solution for the reduced graph
$G^{\prime\prime}_{1}$ if and only if there is a solution for the original
graph $G$; see Claim 1. Then we prove two structural properties about the
degrees of the vertices of $G^{\prime\prime}_{1}$; see Lemmas 1 and 2. These
two properties allow us to bound the size of the “essential” part (called the
core) of the reduced graph $G^{\prime\prime}_{1}$; see Lemma 3.

In the second part of the reduction we remove more redundant vertices of
$G^{\prime\prime}_{1}$ and identify and remove the vertices that necessarily
belong to the solution. Then we show that the resulting reduced graph
$G^{\prime}_{2}$ has size bounded by a polynomial function of the parameter;
see Lemma 4. Finally, we show that there is a solution for $G^{\prime}_{2}$ if
and only if there is a solution for $G^{\prime\prime}_{1}$; see Claim 2. The
proof is concluded by applying an exact algorithm to the graph
$G^{\prime}_{2}$.

##  2 Proof of Theorem 1.1

Let $G=(T\cup B,E)$ be a bipartite graph and $k$ be the number of vertices
that we are allowed to split.

### First reduction rule:

Before we describe our first reduction rule, we make a useful observation.

######  Observation 1.

If a vertex $v\in B$ has at least three neighbours of degree at least two, it
must be split in any planar 2-layered drawing of $G$; see Figure 1(a).

Let $B_{\text{tr}}$ be the set of such vertices of degree 3 or more in $B$ (as
described in Observation 1). The first reduction rule consists of two steps
described below.

  1. 1.

We initialize our solution set $\mathcal{S}$ with the vertices in
$B_{\text{tr}}$, that is, $\mathcal{S}:=B_{\text{tr}}$ and remove them from
the graph $G$. Let the resulting graph be $G^{\prime}_{1}=(T^{\prime}_{1}\cup
B^{\prime}_{1},E^{\prime}_{1})$ and $k^{\prime}_{1}=k-|B_{\text{tr}}|$; note
that $T^{\prime}_{1}=T_{1}$.

  2. 2.

Let $T_{s}\subset T^{\prime}_{1}$ be the set of vertices $v$ such that
deg$(v)=1$ and deg$(u)\geq 3$, where $u$ is the unique neighbor of $v$ in
$G^{\prime}_{1}$. Similarly, let $B_{s}\subset B^{\prime}_{1}$ be the set of
vertices $v$ such that deg$(v)=1$ and deg$(u)\geq 3$, where $u$ is the unique
neighbor of $v$ in $G^{\prime}_{1}$. We remove the vertices $T_{s}$ and
$B_{s}$ from the graph $G^{\prime}_{1}$. Let the resulting graph be
$G^{\prime\prime}_{1}=(T^{\prime\prime}_{1}\cup
B^{\prime\prime}_{1},E^{\prime\prime}_{1})$.

Let us now show the following.

######  Claim 1.

The graph $G$ is a Yes instance for CRSV($k$) if and only if
$G^{\prime\prime}_{1}$ is a Yes instance for CRSV($k_{1}^{\prime}$).

###### Proof.

We first argue the “only if” direction: consider a planar 2-layered drawing of
$G$ with at most $k$ vertices split. According to Observation 1, each vertex
in $B_{\text{tr}}$ is split, moreover, none of the vertices in $B_{s}$ are
split because each of them has degree one. Therefore, there are at most
$k-|B_{\text{tr}}|$ vertices in $B\setminus(B_{\text{tr}}\bigcup B_{s})$ that
are split. Because $B^{\prime\prime}_{1}=B\setminus(B_{\text{tr}}\bigcup
B_{s})$ and $k^{\prime}_{1}=k-|B_{\text{tr}}|$ there exists a planar 2-layered
drawing of $G^{\prime\prime}_{1}$ with at most $k^{\prime}_{1}$ vertices
split.

For the “if” direction, consider a planar 2-layered drawing of
$G^{\prime\prime}_{1}$ with at most $k^{\prime}_{1}$ vertices split. Note that
after applying Step 1 and Step 2 the vertices in $B^{\prime\prime}_{1}$ have
degree at most two. Thus for each vertex $v\in B_{\text{tr}}$ we can reinsert
its split copies $v_{1},v_{2},\dots,v_{\text{deg}{(v)}}$ (each reinserted
vertex has degree one) without crossings; see Figure 1. For the same reason we
can reinsert the vertices in $B_{s}$ of degree one removed at Step 2; see
Figure 2. To see that we can reinsert each vertex $u\in T_{s}$ of degree one
removed at Step 2 observe that we always connect it to a vertex $v\in
B^{\prime\prime}_{1}$ of degree at least two, therefore, in any planar
2-layered drawing of $G^{\prime\prime}_{1}$ there is always a safe wedge
formed by two edges $vv_{1}$ and $vv_{2}$ where we can fit in the edge $vu$
without causing any crossings; see Figure 2. ∎

(a) $v\in B_{\text{tr}}$

(b) a drawing of $G^{\prime\prime}_{1}$

(c) reinserting split copies of $v$

Figure 1:  Reinserting split copies $v_{1},v_{2},\dots,v_{\text{deg}(v)}$ of
$v\in B_{\text{tr}}$ into a planar 2-layered drawing of $G^{\prime\prime}_{1}$
to get a planar 2-layered drawing of $G$.  Figure 2:  Reinserting $w\in B_{s}$
and $u\in T_{s}$ into a 2-layered drawing of $G^{\prime\prime}_{1}$ to obtain
a 2-layered drawing of $G$. A safe wedge $v_{1}vv_{2}$ is filled green.

Now we state two observations about the degrees of the vertices of the graph
$G^{\prime\prime}_{1}$.

######  Lemma 1.

For each vertex $v\in T^{\prime\prime}_{1}$ it holds that deg$(v)\leq
k^{\prime}_{1}+2$ if there exists a planar 2-layered drawing of
$G^{\prime\prime}_{1}$ with at most $k^{\prime}_{1}$ split vertices.

###### Proof.

Consider for contradiction that there is a vertex $v\in T^{\prime\prime}_{1}$
that has deg$(v)=k^{\prime}_{1}+3$; see Figure 3. According to Step 2 $v$ does
not have any neighbors of degree one in $B^{\prime\prime}_{1}$, therefore, to
obtain a planar 2-layered drawing of $G^{\prime\prime}_{1}$ all but two
neighbors of $v$ must be split, that is, $k^{\prime}_{1}+1$ vertices must be
split; contradiction. ∎

Figure 3: All but two neighbors of $v$ must be split to obtain a planar
2-layered drawing of $G^{\prime\prime}_{1}$ because each neighbour of $v$ has
degree at least two.

To make our second observation let $T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq
3}}$ be the set of all the vertices of degree at least three in
$T^{\prime\prime}_{1}$.

######  Lemma 2.

It holds that $\big{|}T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}}\big{|}\leq
2k^{\prime}_{1}$ if there exists a planar 2-layered drawing of
$G^{\prime\prime}_{1}$ with at most $k^{\prime}_{1}$ split vertices.

###### Proof.

Observe that according to Step 2 no vertex in
$T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}}$ has any neighbors of degree
one in $B^{\prime\prime}_{1}$. This implies that for each vertex $v$ in
$T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}}$ at least one of its neighbors
$u\in B^{\prime\prime}_{1}$ must be split to obtain a planar 2-layered drawing
of $G^{\prime\prime}_{1}$; see Figure 4. But the degree of $u$ is at most two,
therefore, splitting $u$ can resolve crossings for at most two vertices
$v_{1},v_{2}\in T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}}$. Thus, if
$|T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}}|>2k^{\prime}_{1}$, more than
$k^{\prime}_{1}$ vertices in $B^{\prime\prime}_{1}$ must be split to obtain a
planar 2-layered drawing of $G^{\prime\prime}_{1}$; contradiction. ∎

Figure 4: For each vertex in $v\in T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq
3}}$ at least one of its neighbors $u\in B^{\prime\prime}_{1}$ must be split
to obtain a planar 2-layered drawing of $G^{\prime\prime}_{1}$ because each of
the neighbours of $v$ has degree at least two. Splitting $u$ can resolve
crossings for at most two vertices $v_{1},v_{2}\in
T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}}$ because it has degree at most
two.

For a subset of vertices $W$ let $N(W)$ denote the set of neighbors of $W$.
From Lemma 1 and 2 we obtain the following.

######  Lemma 3.

The graph induced by the vertices $T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq
3}}\bigcup N(T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}})$ has at most
$2k^{\prime}_{1}(k^{\prime}_{1}+2)$ vertices if there exists a planar
2-layered drawing of $G^{\prime\prime}_{1}$ with at most $k^{\prime}_{1}$
split vertices.

Let $C=T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}}\bigcup
N(T^{\prime\prime}_{1,~{}{\text{deg}(v)\geq 3}})$ and call the graph induced
by the vertices in $C$ the core of $G^{\prime\prime}_{1}$. Now we can proceed
to the second reduction rule.

### Second reduction rule:

Observe that all the vertices in $(B^{\prime\prime}_{1}\bigcup
T^{\prime\prime}_{1})\setminus C$ have degree at most two, and therefore,
induce paths or cycles in $G^{\prime\prime}_{1}$. Since the cycles are not
connected to the core in $G^{\prime\prime}_{1}$ (because their vertices have
degree at most two in $G^{\prime\prime}_{1}$) we can remove them and handle
separately. We need to account for one split vertex per each such cycle. Let
$\mathcal{E}$ be the set of these cycles and let
$k^{\prime}_{2}=k^{\prime}_{1}-|\mathcal{E}|$. In addition, let $Z$ be the set
of vertices that we split in these cycles, $\mathcal{S}:=\mathcal{S}\bigcup
Z$.

Let $\mathcal{P}$ be the set of paths induced in $G^{\prime\prime}_{1}$ by the
vertices in $(B^{\prime\prime}_{1}\bigcup T^{\prime\prime}_{1})\setminus C$ of
length at least $2k^{\prime}_{2}+5$. We reduce $G^{\prime\prime}_{1}$ to
$G^{\prime}_{2}=(T^{\prime}_{2}\cup B^{\prime}_{2},E^{\prime}_{2})$ by
shortening each path $p\in\mathcal{P}$ (that is, iteratively removing one of
the middle vertices of $p$ from $T^{\prime\prime}_{1}$ and identifying its two
neighbours in $B^{\prime\prime}_{1}$) until $p$ has at most
$2k^{\prime}_{2}+5$ vertices. Because during shortening step the length of $p$
decreases by two, after the shortening process $p$ will still have at least
$2k^{\prime}_{2}+3$ vertices.

######  Claim 2.

The graph $G^{\prime\prime}_{1}$ is a Yes instance for CRSV($k^{\prime}_{1}$)
if and only if $G^{\prime}_{2}$ is a Yes instance for CRSV($k^{\prime}_{2}$).

###### Proof.

In one direction the claim is obvious, because shortening paths in a planar
2-layered drawing of the graph $G^{\prime\prime}_{1}$ does not cause any
crossings.

For the other direction, consider a planar 2-layered drawing of the graph
$G^{\prime}_{2}$. To obtain from it a planar 2-layered drawing of the graph
$G^{\prime\prime}_{1}$ we need to: (1) reinsert each of the cycles in
$\mathcal{E}$ that we have removed from $G^{\prime\prime}_{1}$ to obtain
$G^{\prime}_{2}$, and (2) reinsert back the missing parts of the paths of
$\mathcal{P}$, which are made up of the vertices from
$(B^{\prime\prime}_{1}\bigcup T^{\prime\prime}_{1})\setminus C$. Because the
cycles in $\mathcal{E}$ are disconnected from $G^{\prime\prime}_{1}$ we can
reinsert them anywhere in the drawing wherever there is space with one split
vertex in $Z$.

Let us now argue why we can reinsert the missing vertices from
$(B^{\prime\prime}_{1}\bigcup T^{\prime\prime}_{1})\setminus C$ into the paths
in $\mathcal{P}$; we will refer to Figure 5 for illustration. Because for any
such path $p\in\mathcal{P}$ the length of $p$ is at least $2k^{\prime}_{2}+3$
there must be at least one vertex $v$ in $B^{\prime}_{2}$ that was not split
in a planar 2-layered drawing of $G^{\prime}_{2}$ (see Figure 5(a)), as
otherwise a planar 2-layered drawing of $G^{\prime}_{2}$ cannot be constructed
with at most $k^{\prime}_{2}$ splits. Therefore, there must be a safe wedge
formed by the unsplit vertex $v$ and the two edges of the path $p$ incident to
$v$ providing space to reinsert the missing vertices without causing any
crossings; see Figure 5(b). ∎

(a) $p$ (black) in $G^{\prime}_{2}$, safe wedge (green)

(b) reinserting the missing part of $p$

Figure 5: Reinserting the missing part of the path $p\in\mathcal{P}$ into a
planar 2-layered drawing of $G^{\prime}_{2}$ to get a planar 2-layered drawing
of $G^{\prime\prime}_{1}$.

######  Lemma 4.

The graph $G^{\prime}_{2}$ has at most $O(k^{6})$ vertices.

###### Proof.

According to Lemma 3 the core $C$ has at most
$2k^{\prime}_{1}(k^{\prime}_{1}+2)$ vertices and according to Lemma 1 the
highest degree of each vertex in $C$ is at most $k^{\prime}_{1}+2$. Therefore,
there can be at most
${{2k^{\prime}_{1}(k^{\prime}_{1}+2)}\choose{2}}(k^{\prime}_{1}+2)$ many paths
induced by the vertices in $(B^{\prime}_{2}\bigcup T^{\prime}_{2})\setminus
C$. Moreover, after applying the second reduction rule each such path has at
most $2k^{\prime}_{2}+5$ vertices. Thus the total number of vertices in
$G^{\prime}_{2}$ is at most
${{2k^{\prime}_{1}(k^{\prime}_{1}+2)}\choose{2}}(k^{\prime}_{1}+2)(2k^{\prime}_{2}+5)\in
O(k^{6})$. ∎

Finally we decide CRSV($k^{\prime}_{2}$) for $G^{\prime}_{2}$ by brute force.
More precisely, we check all subsets $X$ of $B^{\prime}_{2}$ such that
$|X|\leq k^{\prime}_{2}\leq k$. For each vertex $v$ in $X$ we check all ways
to partition its incident edges (at most $k+2$) into non-empty subsets, this
represents splitting of $v$. The number of such partitions is bounded by the
Bell number of order $k+2$, which in turn is bounded by $(k+2)!$. Then we run
a linear time algorithm to check whether a planar 2-layered drawing of the
resulting graph exists. This can be done in time $2^{O(k^{6})}(k!)^{O(k)}\cdot
m\subset 2^{O(k^{6})}\cdot m$, where $m$ is the number of edges of $G$. If
$G^{\prime}_{2}$ is a yes instance for CRSV($k^{\prime}_{2}$) with the subset
of split vertices $X$, we update our solution set
$\mathcal{S}:=\mathcal{S}\bigcup X$ and return it. It is worth noting that the
kernelization itself can be done in time $O(m)$ since we process each vertex
in constant time given that we know its degree. Thus, the kernelization does
not affect the total asymptotic runtime of the algorithm.

##  3 Conclusion and Open Problems

We presented an FPT algorithm for the CRSV($k$) problem parameterized by $k$.
Improving the runtime is needed for this algorithm to be useful in practice,
as the constants are very large. Another natural direction is to look for an
FPT algorithm for the other variant of the problem, that is, minimizing the
number of splits, which was recently shown to be NP-hard [1].

######  Problem (Crossing Removal with $\boldsymbol{k}$ Splits – CRS($k$)).

Let $G=(T\cup B,E)$ be a bipartite graph. Decide whether there is a planar
2-layer drawing of $G$ after applying at most $k$ splits to the vertices in
$B$.

Is there an FPT algorithm for the CRS($k$) problem parameterized by $k$? It is
not clear how to adjust the algorithm in Theorem 1.1 as it splits every vertex
in $B_{\text{tr}}$ as many times as its degree, and thus, the number of splits
is not bounded by a function of the parameter $k$.

## References

  * [1] Ahmed, R., Angelini, P., Bekos, M.A., Battista, G.D., Kaufmann, M., Kindermann, P., Nöllenburg, M., Symvonis, A., Villedieu, A., Wallinger, M.: Splitting Vertices in 2-Layer Graph Drawings (2022), [unpublished manuscript]
  * [2] Börner, K., Kobourov, S.: Multi-Level Graph Representation for Big Data Arising in Science Mapping (Dagstuhl Seminar 21152). Dagstuhl Reports 11(3), 1–15 (2021). https://doi.org/10.4230/DagRep.11.3.1, https://drops.dagstuhl.de/opus/volltexte/2021/14688
  * [3] Chaudhary, A., Chen, D.Z., Hu, X.S., Niemier, M.T., Ravichandran, R., Whitton, K.: Fabricatable interconnect and molecular QCA circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 26(11), 1978–1991 (2007)
  * [4] Dujmović, V., Fernau, H., Kaufmann, M.: Fixed parameter algorithms for one-sided crossing minimization revisited. Journal of Discrete Algorithms 6(2), 313–323 (2008)
  * [5] Dujmović, V., Whitesides, S.: An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. Algorithmica 40(1), 15–31 (2004)
  * [6] Eades, P., McKay, B.D., Wormald, N.C.: On an edge crossing problem. In: Proc. 9th Australian Computer Science Conference. vol. 327, p. 334 (1986)
  * [7] Eades, P., de Mendonça N., C.F.X.: Vertex-splitting and tension-free layouts. In: GD ’95. vol. 1027, pp. 202–211. Springer (1996)
  * [8] Eppstein, D., Kindermann, P., Kobourov, S., Liotta, G., Lubiw, A., Maignan, A., Mondal, D., Vosoughpour, H., Whitesides, S., Wismath, S.: On the planar split thickness of graphs. Algorithmica 80, 977–994 (2018)
  * [9] Faria, L., de Figueiredo, C.M.H., Mendonça, C.F.X.: Splitting number is NP-complete. DAM 108(1), 65–83 (2001)
  * [10] Fernau, H., Fomin, F.V., Lokshtanov, D., Mnich, M., Philip, G., Saurabh, S.: Ranking and drawing in subexponential time. In: International Workshop on Combinatorial Algorithms. pp. 337–348. Springer (2010)
  * [11] Impagliazzo, R., Paturi, R.: On the complexity of k-sat. Journal of Computer and System Sciences 62(2), 367–375 (2001)
  * [12] Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. JGAA 1(1), 1–25 (1997)
  * [13] Knauer, K., Ueckerdt, T.: Three ways to cover a graph. DM 339(2), 745–758 (2016)
  * [14] Kobayashi, Y., Tamaki, H.: A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization. In: European Symposium on Algorithms. pp. 683–694. Springer (2012)
  * [15] Liebers, A.: Planarizing graphs – a survey and annotated bibliography. JGAA 5(1), 1–74 (2001)
  * [16] Muñoz, X., Unger, W., Vrt’o, I.: One sided crossing minimization is np-hard for sparse graphs. In: International Symposium on Graph Drawing. pp. 115–123. Springer (2001)
  * [17] Nagamochi, H.: An improved approximation to the one-sided bilayer drawing. In: International Symposium on Graph Drawing. pp. 406–418. Springer (2003)
  * [18] Nickel, S., Nöllenburg, M., Sorge, M., Villedieu, A., Wu, H.Y., Wulms, J.: Planarizing graphs and their drawings by vertex splitting (2022). https://doi.org/10.48550/ARXIV.2202.12293, https://arxiv.org/abs/2202.12293
  * [19] Paul, H., Börner, K., Herr II, B.W., Quardokus, E.M.: ASCT+B REPORTER. https://hubmapconsortium.github.io/ccf-asct-reporter/ (2022), [Online; accessed 06-June-2022]
  * [20] Pavlopoulos, G.A., Kontou, P.I., Pavlopoulou, A., Bouyioukos, C., Markou, E., Bagos, P.G.: Bipartite graphs in systems biology and medicine: a survey of methods and applications. GigaScience 7(4), giy014 (2018)