Colgate University, Hamilton, NY, USA John Cabot University, Rome, Italy
University of Ioannina, Ioannina, Greece Roma Tre University, Rome, Italy
Universität Tübingen, Tübingen, Germany Universität Trier, Trier, Germany
University of Arizona, Tucson, AZ, USA TU Wien, Vienna, Austria NTUA, Athens,
Greece TU Wien, Vienna, Austria TU Wien, Vienna, Austria R. Ahmed, P.
Angelini, M. A. Bekos, G. D. Battista, M. Kaufmann, P. Kindermann, S.
Kobourov, M. Nöllenburg, A. Symvonis, A. Villedieu, M. Wallinger [300]Theory
of computation Design and analysis of algorithms 1

#  Splitting Vertices in 2-Layer Graph Drawings

Reyan Ahmed  Patrizio Angelini  Michael A. Bekos  Giuseppe Di Battista
Michael Kaufmann  Philipp Kindermann  Stephen Kobourov  Martin Nöllenburg
Antonios Symvonis  Anaïs Villedieu  Markus Wallinger

###### Abstract

Bipartite graphs model the relationships between two disjoint sets of entities
in several applications and are naturally drawn as 2-layer graph drawings. In
such drawings, the two sets of entities (vertices) are placed on two parallel
lines (layers), and their relationships (edges) are represented by segments
connecting vertices. Methods for constructing 2-layer drawings often try to
minimize the number of edge crossings. We use vertex splitting to reduce the
number of crossings, by replacing selected vertices on one layer by two (or
more) copies and suitably distributing their incident edges among these
copies. We study several optimization problems related to vertex splitting,
either minimizing the number of crossings or removing all crossings with
fewest splits. While we prove that some variants are -complete, we obtain
polynomial-time algorithms for others. We run our algorithms on a benchmark
set of bipartite graphs representing the relationships between human
anatomical structures and cell types.

###### keywords:

2-layer graph drawings, vertex splitting, edge crossings

##  1 Introduction

Multilayer networks are used in many applications to model complex
relationships between different sets of entities in interdependent subsystems
[19]. When analyzing and exploring the interaction between two such subsystems
$S_{t}$ and $S_{b}$, bipartite or 2-layer networks arise naturally. The nodes
of the two subsystem are modeled as a bipartite vertex set $V=V_{t}\cup V_{b}$
with $V_{t}\cap V_{b}=\emptyset$, where $V_{t}$ contains the vertices of the
first subsystem $S_{t}$ and $V_{b}$ those of $S_{b}$. The inter-layer
connections between $S_{t}$ and $S_{b}$ are modeled as an edge set $E\subseteq
V_{t}\times V_{b}$, forming a bipartite graph $G=(V_{t}\cup V_{b},E)$.
Visualizing this bipartite graph $G$ in a clear and understandable way is then
a key requirement for designing tools for visual network analysis [21].

A layered graph is a natural representation of the relationships between
different genomic components, such as cell types and genes/proteins. Graphs of
this type can be obtained using massively parallel sequencing in bulk at the
single-cell level [3]. Börner et al. [3] studied different tasks expected to
be performed on such graphs (e.g., finding neighbors, finding shared
neighbors, etc.).

In a _2-layer graph drawing_ of a bipartite graph the vertices are drawn as
points on two distinct parallel lines $\ell_{t}$ and $\ell_{b}$, and edges are
drawn as straight-line segments [9]. The vertices in $V_{t}$ (_top vertices_)
lie on $\ell_{t}$ (_top layer_) and those in $V_{b}$ (_bottom vertices_) lie
on $\ell_{b}$ (_bottom layer_). In addition to direct applications of 2-layer
networks for modeling the relationships between two communities as mentioned
above [21], such drawings also occur in tanglegram layouts for comparing
phylogenetic trees [23] or as components in layered drawings of directed
graphs [24].

Purchase [22] has studied different graph layout properties that have an
impact on human understanding. In particular, it is known that edge crossings
can significantly impact graph-based tasks, which is why minimizing the number
of edge crossings (or removing all edge crossings altogether) is of interest.

The primary optimization goal for 2-layer graph drawings is to find
permutations of one or both vertex sets $V_{t}$, $V_{b}$ to minimize the
number of edge crossings. While the existence of a crossing-free 2-layer
drawing can be tested in linear time [7], the crossing minimization problem is
-complete even if the permutation of one layer is given [9]. Hence, both
fixed-parameter algorithms [17] and approximation algorithms [5] have been
published. Further, graph layouts on two layers have also been widely studied
in the area of graph drawing beyond planarity [6]. However, from a practical
point of view, minimizing the number of crossings in 2-layer drawings may
still result in visually complex drawings [15].

Hence, in this paper, as an alternative approach to construct readable 2-layer
drawings, we study vertex splitting [8, 18, 10, 16]. The _vertex-split_
operation (or _split_ , for simplicity) for a vertex $v$ deletes $v$ from $G$,
adds two new copies $v_{1}$ and $v_{2}$ (in the original vertex subset of
$G$), and distributes the edges originally incident to $v$ among the two new
vertices $v_{1}$ and $v_{2}$. Placing $v_{1}$ and $v_{2}$ independently in the
2-layer drawing can in turn reduce the number of crossings.

Vertex splitting has been studied in the context of the _splitting number_ of
an arbitrary graph $G$, which is the smallest number of vertex-splits needed
to transform $G$ into a planar graph. The splitting number problem is
-complete, even for cubic graphs [11], but the splitting numbers of complete
and complete bipartite graphs are known [12, 14]. Vertex splitting has also
been studied in the context of _split thickness_ , which is the minimum
maximum number of splits per vertex to obtain a graph with a certain property,
e.g., a planar graph or an interval graph [10].

In this paper we consider reducing or removing edge crossings by vertex
splitting. Vertex splitting is a useful technique to visualize complex pathway
graphs of biological mechanisms. Nielsen et al. [20] have proposed an approach
using Machine Learning to facilitate the visualization of pathway graphs by
training a Support Vector Machine with actions taken during manual
biocuration. Henry et al. [13] have improved the readability of clustered
social networks using vertex splitting. These studies demonstrate the
importance of vertex splitting for visualizing complex networks.

We study variations of the algorithmic problem of constructing planar or
crossing-minimal 2-layer drawings with vertex splitting. In visualizing graphs
defined on anatomical structures and cell types in the human body [1], the two
vertex sets of $G$ play different roles and vertex splitting is permitted only
on one side of the layout. This motivates our interest in splitting only the
bottom vertices. The top vertices may either be specified with a given
context-dependent input ordering, e.g., alphabetically, following a hierarchy
structure, or sorted according to an important measure, or we may be allowed
to arbitrarily permute them to perform fewer vertex splits.

###  1.1 Contributions

We prove that for a given integer $k$ it is -complete to decide whether $G$
admits a planar 2-layer drawing with an arbitrary permutation on the top layer
and at most $k$ vertex splits on the bottom layer (see Theorem 3.1).
-completeness also holds if at most $k$ vertices can be split, but each an
arbitrary number of times (see Theorem 4.1).

If, however, the vertex order of $V_{t}$ is given, then we present two linear-
time algorithms to compute planar 2-layer drawings, one minimizing the total
number of splits (see Theorem 3.3), and one minimizing the number of split
vertices (see Theorem 4.2). In view of their linear-time complexity, our
algorithms may be useful for practical applications; we perform an
experimental evaluation of the algorithm for Theorem 3.3 using real-world data
sets stemming from anatomical structures and cell types in the human body [1].

We further study the setting in which the goal is to minimize the number of
crossings (but not necessarily remove all of them) using a prescribed total
number of splits. For this setting, we prove -completeness even if the vertex
order of $V_{t}$ is given (see Theorem 5.1). On the other hand, we provide an
-time algorithm parameterized by the number of allowed splits (see Theorem
5.3), which, in other words, means that the algorithm has a polynomial running
time for any fixed number of allowed splits.

##  2 Preliminaries

We denote the order of the vertices in $V_{t}$ and $V_{b}$ in a $2$-layer
drawing by $\pi_{t}$ and $\pi_{b}$, resp. If a vertex $u$ precedes a vertex
$v$, then we denote it by $u\prec v$. Although $2$-layer drawings are defined
geometrically, their crossings are fully described by $\pi_{t}$ and $\pi_{b}$,
as in the following folklore lemma.

######  Lemma 2.1.

Let $\Gamma$ be a 2-layer drawing of a bipartite graph $G=(V_{t}\cup
V_{b},E)$. Let $(v_{1},u_{1})$ and $(v_{2},u_{2})$ be two edges of $E$ such
that $v_{1}\prec v_{2}$ in $\pi_{t}$. Then, edges $(v_{1},u_{1})$ and
$(v_{2},u_{2})$ cross each other in $\Gamma$ if and only if $u_{2}\prec u_{1}$
in $\pi_{b}$.

In the following we formally define the problems we study. For all of them,
the input contains a bipartite graph $G=(V_{t}\cup V_{b},E)$ and a split
parameter $k$.

  * •

Crossing Removal with $\boldsymbol{k}$ Splits – CRS($\boldsymbol{k}$): Decide
if there is a planar 2-layer drawing of $G$ after applying at most $k$ vertex-
splits to the vertices in $V_{b}$.

  * •

Crossing Removal with $\boldsymbol{k}$ Split Vertices –
CRSV($\boldsymbol{k}$): Decide if there is a planar 2-layer drawing of $G$
after splitting at most $k$ original vertices of $V_{b}$.

  * •

Crossing Minimization with $\boldsymbol{k}$ Splits –
CMS($\boldsymbol{k},\boldsymbol{M}$): Decide if there is a 2-layer drawing of
$G$ with at most $M$ crossings after applying at most $k$ vertex-splits to the
vertices in $V_{b}$, where $M$ is an additional integer specified as part of
the input.

Note that in CRSV($k$), once we decide to split an original vertex, then we
can further split its copies without incurring any additional cost. The
example in Figure 1(a)–1(c) demonstrates the difference between CRS and CRSV.

For all problems, we refer to the variant where the order $\pi_{t}$ of the
vertices in $V_{t}$ is given as part of the input by adding the suffix _“with
Fixed Order”_.

(a) Instance $G$.

(b) Optimal CRS solution of $G$ with three splits of three different vertices.

(c) Optimal CRSV solution of $G$ with two split vertices.

(d) Subdivided graph $G^{\prime}$.

(e) Instance of CRS($k$) for $G^{\prime}$.

(f) Splits are minimized if and only if $G$ has a Hamiltonian path.

(g) Case 1.

(h) Case 2.

(i) Case 3.

Figure 1: Differences between CRS and CRSV problems (a)–(c); illustrations for
the reduction in Theorem 3.1 (d)–(f); illustrations for the optimization
algorithm for CRS($k$) with Fixed Order, where vertices in $N^{+}$ are colored
in shades of gray (g)–(i).

The following lemma implies conditions under which a vertex split must occur.

######  Lemma 2.2.

Let $G=(V_{t}\cup V_{b},E)$ be a bipartite graph and let $u\in V_{b}$ be a
bottom vertex adjacent to two top vertices $v_{1},v_{2}\in V_{t}$, with
$v_{1}\prec v_{2}$ in $\pi_{t}$. In any planar 2-layer drawing of $G$ in which
$u$ is not split, we have that:

  1. C.1

A top vertex that appears between $v_{1}$ and $v_{2}$ in $\pi_{t}$ can only be
adjacent to $u$;

  2. C.2

In $\pi_{b}$, $u$ is the last neighbor of $v_{1}$ and the first neighbor of
$v_{2}$.

######  Proof 2.3.

If there is a top vertex $v^{\prime}$ between $v_{1}$ and $v_{2}$ adjacent to
a bottom vertex $u^{\prime}\neq u$, then $(v^{\prime},u^{\prime})$ crosses
$(v_{1},u)$ or $(v_{2},u)$. If there is a neighbor $u^{\prime\prime}$ of
$v_{1}$ after $u$ in $\pi_{b}$, then the edges $(v_{1},u^{\prime\prime})$ and
$(v_{2},u)$ cross. A symmetric argument holds when there is a neighbor of
$v_{2}$ before $u$ in $\pi_{b}$.

##  3 Crossing Removal with $\boldsymbol{k}$ Splits

In this section, we prove that the CRS($k$) problem is -complete in general
and linear-time solvable when the order $\pi_{t}$ of the top vertices is part
of the input.

######  Theorem 3.1.

The CRS($k$) problem is -complete.

######  Proof 3.2.

The problem belongs to since, given a set of at most $k$ splits for the
vertices in $V_{b}$, we can check whether the resulting graph is planar
$2$-layer [7].

We use a reduction from the _Hamiltonian Path_ problem to show the -hardness.
Given an instance $G=(V,E)$ of the Hamiltonian Path problem, we denote by
$G^{\prime}$ the bipartite graph obtained by subdividing every edge of $G$
once (Figure 1(d)). We construct an instance of the CRS($k$) problem (Figure
1(e)) by setting the top vertex set $V_{t}$ to consist of the original
vertices of $G$, the bottom vertex set $V_{b}$ to consist of the subdivision
vertices of $G^{\prime}$, and the split parameter to $k=|E|-|V|+1$. The
reduction can be easily performed in linear time. We prove the equivalence.

Suppose that $G$ has a Hamiltonian path $v_{1},\dots,v_{n}$. Set
$\pi_{t}=v_{1},\dots,v_{n}$, and split all the vertices of $V_{b}$, except for
the subdivision vertex of the edge $(v_{i},v_{i+1})$, for each $i=1,\dots,n-1$
(Figure 1(f)). This results in $|V_{b}|-(n-1)$ splits, which is equal to $k$,
since $|V_{b}|=|E|$ and $n=|V|$. We then construct $\pi_{b}$ such that, for
each $i=1,\dots,n-1$, all the neighbors of $v_{i}$ appear before all the
neighbors of $v_{i+1}$, with their common neighbor being the last neighbor of
$v_{i}$ and the first of $v_{i+1}$. This guarantees that both conditions of
Lemma 2.2 are satisfied for every vertex of $V_{b}$. Together with Lemma 2.1,
this guarantees that the 2-layer drawing is planar.

Suppose now that $G^{\prime}$ admits a planar 2-layer drawing with at most
$|E|-|V|+1$ splits. Since $|E|=|V_{b}|$ and every vertex of $V_{b}$ has degree
exactly $2$ (subdivision vertices), there exist at least $|V|-1$ vertices in
$V_{b}$ that are not split. Consider any such vertex $u\in V_{b}$. By C.1 of
Lemma 2.2, the two neighbors of $u$ are consecutive in $\pi_{t}$. Also, these
vertices are connected in $G$ by the edge whose subdivision vertex is $u$.
Since this holds for each of the at least $|V|-1$ non-split vertices, we have
that each of the $|V|-1$ distinct pairs of consecutive vertices in $V_{t}$
(recall that $V_{t}=V$) is connected by an edge in $G$. Thus, $G$ has a
Hamiltonian path.

Next, we focus on the optimization version of the CRS($k$) with the Fixed
Order problem. Our recursive algorithm considers a constrained version of the
problem, where the first neighbor in $\pi_{b}$ of the first vertex in
$\pi_{t}$ may be prescribed. At the outset of the recursion, there exists no
prescribed first neighbor. The algorithm returns the split vertices in $V_{b}$
and the corresponding order $\pi_{b}$.

In the base case, there is only one top vertex $v$, i.e., $|V_{t}|=1$. Since
all vertices in $V_{b}$ have degree $1$, no split takes place. We set
$\pi_{b}$ to be any order of the vertices in $V_{b}$ where the first vertex is
the prescribed first neighbor of $v$, if any.

In the recursive case when $|V_{t}|>1$, we label the vertices in $V_{t}$ as
$v_{1},\dots,v_{|V_{t}|}$, according to $\pi_{t}$. If the first neighbor of
$v_{1}$ is prescribed, we denote it by $u_{1}^{*}$. Also, we denote by $N^{1}$
the set of degree-$1$ neighbors of $v_{1}$, and by $N^{+}$ the other neighbors
of $v_{1}$. Note that only the vertices in $N^{+}$ are candidates to be split
for $v_{1}$. In particular, by C.1 of Lemma 2.2, a vertex in $N^{+}$ can avoid
being split only if it is also incident to $v_{2}$. Further, since any vertex
in $N^{+}$ that is not split must be the last neighbor of $v_{1}$ in
$\pi_{b}$, by C.2 of Lemma 2.2, at most one of the common neighbors of $v_{1}$
and $v_{2}$ will not be split. Analogously, if $u_{1}^{*}$ is prescribed, then
it must be split, unless $v_{1}$ has degree $1$.

In view of these properties, we distinguish three cases based on the common
neighborhood of $v_{1}$ and $v_{2}$. In all cases, we will recursively compute
a solution for the instance composed of the graph
$G^{\prime}=(V_{t}^{\prime}\cup V_{b}^{\prime},E^{\prime})$ obtained by
removing $v_{1}$ and the vertices in $N^{1}$ from $G$, and of the order
$\pi_{t}^{\prime}=v_{2},\dots,v_{|V_{t}|}$. We denote by $\pi_{b}^{\prime}$
and $s^{\prime}$ the computed order and the number of splits for the vertices
in $V_{b}^{\prime}$. In the following we specify for each case whether the
first neighbor of $v_{2}$ in the new instance is prescribed or not, and how to
incorporate the neighbors of $v_{1}$ into $\pi_{b}^{\prime}$.

Case 1: $v_{1}$ and $v_{2}$ have no common neighbor; see Figure 1(g). In this
case, we do not prescribe the first neighbor of $v_{2}$ in the instance
composed of $G^{\prime}$ and $\pi_{t}^{\prime}$. To compute a solution for the
original instance, we split each vertex in $N^{+}$ so that one copy becomes
incident only to $v_{1}$. We construct $\pi_{b}$ by selecting the prescribed
vertex $u_{1}^{*}$, if any, followed by the remaining neighbors of $v_{1}$ in
any order and, finally, by appending $\pi_{b}^{\prime}$. This results in
$s=|N^{+}|+s^{\prime}$ splits.

Case 2: $v_{1}$ and $v_{2}$ have exactly one common neighbor $u$. If
$u=u_{1}^{*}$ and $v_{1}$ have a degree larger than $1$, then $u$ cannot be
the last neighbor of $v_{1}$ and must be split. Thus, we perform the same
procedure as in Case 1. Otherwise, in the instance composed of $G^{\prime}$
and $\pi_{t}^{\prime}$, we set $u$ as the prescribed first neighbor of
$v_{2}$; bluesee Figure 1(h). To compute a solution for the original instance,
we split each vertex in $N^{+}$, except $u$, so that one copy becomes incident
only to $v_{1}$. We construct $\pi_{b}$ by selecting the prescribed vertex
$u_{1}^{*}$, if any, followed by the remaining neighbors of $v_{1}$ different
from $u$ in any order and, finally, by appending $\pi_{b}^{\prime}$. This
results in $s=|N^{+}|-1+s^{\prime}$ splits.

Case 3: $v_{1}$ and $v_{2}$ have more than one common neighbor. If $v_{1}$ and
$v_{2}$ have exactly two common neighbors $u,u^{\prime}$ and one of them is
$u_{1}^{*}$, say $u=u_{1}^{*}$, then $u$ cannot be the last neighbor of
$v_{1}$, as $v_{1}$ has degree larger than $1$. Thus, we proceed exactly as in
Case 2, using $u^{\prime}$ as the only common neighbor of $v_{1}$ and $v_{2}$.

Otherwise, there are at least two neighbors of $v_{1}$ different from
$u_{1}^{*}$; see Figure 1(i). We want to choose one of these vertices as the
last neighbor of $v_{1}$, so that it is not split. However, the choice is not
arbitrary as this may affect the possibility for $v_{2}$ to save the split for
a neighbor it shares with $v_{3}$. In the instance composed of $G^{\prime}$
and $\pi_{t}^{\prime}$, we do not prescribe the first vertex of $v_{2}$. To
compute a solution for the original instance, we simply choose as the last
neighbor of $v_{1}$ any of its common neighbors with $v_{2}$ that has not been
set as the last neighbor of $v_{2}$ in $\pi_{b}^{\prime}$. Such a vertex, say
$u$, always exists since $v_{1}$ and $v_{2}$ have at least two common
neighbors different from $u_{1}^{*}$, and can be moved to become the first
vertex in $\pi_{b}^{\prime}$. Specifically, we split all the vertices in
$N^{+}$, except for $u$, so that one copy becomes incident only to $v_{1}$. We
construct $\pi_{b}$ by selecting the prescribed vertex $u_{1}^{*}$, if any,
followed by the remaining neighbors of $v_{1}$ different from $u$ in any
order. We then modify $\pi_{b}^{\prime}$ by moving $u$ to be the first vertex.
Note that this operation does not affect planarity, as it only involves
reordering the set of consecutive degree-$1$ vertices incident to $v_{2}$.
Finally, we append the modified $\pi_{b}^{\prime}$. This results in
$s=|N^{+}|-1+s^{\prime}$ splits.

######  Theorem 3.3.

For a bipartite graph $G=(V_{t}\cup V_{b},E)$ and an order $\pi_{t}$ of
$V_{t}$, the optimization version of CRS($k$) with Fixed Order can be solved
in $O(|E|)$ time.

######  Proof 3.4.

By construction, for each $i=1,\dots,|V_{t}|-1$, all neighbors of $v_{i}$
precede all neighbors of $v_{i+1}$ in $\pi_{b}$. Thus, by Lemma 2.1, the
drawing is planar. The minimality of the number of splits follows from Lemma
2.2, as discussed before the case distinction. In particular, any minimum-
splits solution can be shown to be equivalent to the one produced by our
algorithm. The time complexity follows as each vertex only needs to check its
neighbors a constant number of times.

Algorithm 1 CRS($k$)-with-Fixed-Order($V_{t},V_{b},\pi_{t}$)

if there is only one vertex in $V_{t}$ then

Let $N(v)$ be the neighbor vertices of $v$

Output an arbitrary order $N(v)$

else

Let $v_{1}$ and $v_{2}$ are the first two vertices in $V_{t}$

if $N(v_{1})\cap N(v_{2})\neq\emptyset$ then

Let $N^{+}(v_{1})$ be the set of neighbors of $v_{1}$ having degree more than
one

let $\pi_{b}^{\prime}$ be the output of CRS($k$)-with-Fixed-
Order($V_{t}-v_{1},V_{b},\pi_{t}-v_{1}$)

Find a common neighbor $u$ of $v_{1}$ and $v_{2}$ not in $\pi_{b}^{\prime}$

output $u,\pi_{b}^{\prime}$

else

let $\pi_{b}^{\prime}$ be the output of CRS($k$)-with-Fixed-
Order($V_{t}-v_{1},V_{b},\pi_{t}-v_{1}$)

Output $N(v_{1}),\pi_{b}^{\prime}$

end if

end if

We conclude this section by mentioning that the CRS($k$) problem had already
been considered, under a different terminology, in the context of molecular
QCA circuits design [4]. Here, the problem was claimed to be -complete,
without providing a formal proof. In the same work, when the order $\pi_{t}$
of the top vertices is part of the input, an alternative algorithm was
proposed based on the construction of an auxiliary graph that has super-linear
size. Exploiting linear-time sorting algorithms and observations that allow
avoiding explicitly constructing all edges of this graph, the authors were
able to obtain a linear-time implementation. We believe that our algorithm of
Theorem 3.3 is simpler and more intuitive, and directly leads to a linear-time
implementation.

##  4 Crossing Removal with $\boldsymbol{k}$ Split Vertices

In this section, we prove that the CRSV($k$) problem is -complete in general
and linear-time solvable when the order $\pi_{t}$ of the top vertices is part
of the input. Ahmed et al. [2] showed that CRSV($k$) is when parameterized by
$k$. To prove the -completeness we can use the reduction of Theorem 3.1. In
fact, in the graphs produced by that reduction all vertices in $V_{b}$ have
degree $2$. Hence, the number of vertices that are split coincides with the
total number of splits.

######  Theorem 4.1.

The CRSV($k$) problem is -complete.

For the version with Fixed Order, we first use C.1 of Lemma 2.2 to identify
vertices that need to be split at least once, and repeatedly split them until
each has degree $1$. For a vertex $u\in V_{b}$, we can decide if it needs to
be split by checking whether its neighbors are consecutive in $\pi_{t}$ and,
if $u$ has degree at least $3$, all its neighbors different from the first and
last have degree exactly $1$.

We first perform all necessary splits. For each $i=1,\dots,|V_{t}|-1$,
consider the two consecutive top vertices $v_{i}$ and $v_{i+1}$. If they have
no common neighbor, no split is needed. If they have exactly one common
neighbor $u$, then we set $u$ as the last neighbor of $v_{i}$ and the first of
$v_{i+1}$, which allows us not to split $u$, according to C.2. Since $u$ did
not participate in any necessary split, if $u$ is also adjacent to other
vertices, then all its neighbors have degree $1$, except possibly the first
and last. Hence, C.2 can be guaranteed for all pairs of consecutive neighbors
of $u$.

Otherwise, $v_{i}$ and $v_{i+1}$ have at least two common neighbors and thus
have degree at least $2$. Hence, all common neighbors of $v_{i}$ and $v_{i+1}$
must be split, except for at most one, namely the one that is set as the last
neighbor of $v_{i}$ and as the first of $v_{i+1}$. Since all these vertices
are incident only to $v_{i}$ and $v_{i+1}$, as otherwise they would have been
split by C.1, we can arbitrarily choose any of them, without affecting the
splits of other vertices.

Algorithm 2 CRSV($k$)-with-Fixed-Order($V_{t},V_{b},\pi_{t}$)

for $i=1,\cdots,|V_{t}|-1$ do

if $v_{i}$ and $v_{i+1}$ has no common neighbors then

No split is needed

end if

if $v_{i}$ and $v_{i+1}$ has exactly one common neighbor then

Let $u$ be the common neighbor

if $u$ is also adjacent to other vertices that has degree 1 except the first
an last one then

No split is needed

else

Split $u$ when mandatory

end if

else

Split all common neighbors except at most once

end if

end for

At the end we construct the order $\pi_{b}$ so that, for each
$i=1,\dots,|V_{t}|-1$, all the neighbors of $v_{i}$ precede all the neighbors
of $v_{i+1}$, and the unique common neighbor of $v_{i}$ and $v_{i+1}$, if any,
is the last neighbor of $v_{i}$ and the first of $v_{i+1}$. By Lemma 2.1, this
guarantees planarity. Identifying and performing all unavoidable splits and
computing $\pi_{b}$ can be easily done in $O(|E|)$ time. Since we only
performed unavoidable splits, as dictated by Lemma 2.2, we have the following.

######  Theorem 4.2.

For a bipartite graph $G=(V_{t}\cup V_{b},E)$ and an order $\pi_{t}$ of
$V_{t}$, the optimization version of CRSV($k$) with Fixed Order minimizing the
number of split vertices can be solved in $O(|E|)$ time.

##  5 Crossing Minimization with $\boldsymbol{k}$ Splits

In this section we consider minimizing crossings (not necessarily removing
all), by applying at most $k$ splits. We first prove -completeness of the
decision problem CMS($k,M$) with Fixed Order and then give a polynomial-time
algorithm assuming the integer $k$ is a constant.

######  Theorem 5.1.

For a bipartite graph $G=(V_{t}\cup V_{b},E)$, an order $\pi_{t}$ of $V_{t}$,
and integers $k,M$, problem CMS($k,M$) with Fixed Order is -complete.

######  Proof 5.2.

We reduce from the -complete Decision Crossing Problem (DCP) [9], where given
a bipartite 2-layer graph with one vertex order fixed, the goal is to find an
order of the other set such that the number of crossings is at most a given
integer $M$. Given an instance of DCP, i.e.,a 2-layer graph $G=(V_{t}\cup
V_{b},E)$, with ordering $\pi_{t}$ of $V_{t}$ and integer $M$, we construct an
instance $G^{\prime}$ of CMS($k,M$) where $k=|V_{b}|$. First let
$G^{\prime}=(V^{\prime}_{t}\cup V^{\prime}_{b},E^{\prime})$ be a copy of $G$.
We give an arbitrary ordering $\pi_{b}$ to the vertices of $V^{\prime}_{b}$.
We then add, respectively, to each vertex set $V_{t}$ and $V_{b}$ a set
$U_{t}$ and $U_{b}$ of $M+1$ vertices and connect each $u\in U_{t}$ to exactly
one $v\in U_{b}$, forming a matching of size $M+1$. We add the vertices of
$U_{t}$ to $\pi_{t}$ (resp. $U_{b}$ to $\pi_{b}$) after all the vertices of
$V_{t}$ ($V_{b})$. We lastly add a set $W_{t}$ of $k$ vertices to
$V^{\prime}_{t}$, placed at the end of $\pi_{t}$, such that each $w_{i}\in
W_{t}$ ($i=1,\dots,k$) has exactly one neighbor $v_{i}\in V_{b}$ and vice
versa; see Figure 2(a).

Given an ordering $\pi_{b}^{*}$ of $V_{b}$ that results in a drawing of $G$
with at most $M$ crossings, we show that we can solve the CMS($k,M$) instance
$G^{\prime}$. In $G^{\prime}$, we split each vertex of $V_{b}$ to obtain the
sets $V_{b}^{1}$ and $V_{b}^{2}$ in which we place exactly one copy of each
original vertex. We place $V_{b}^{2}$ after the vertices of $U_{b}$ in
$\pi_{b}$ in the same order that the vertices of $W_{t}$ appear in $\pi_{t}$
and draw a single edge between the copies and their neighbor in $W_{t}$. We
place $V_{b}^{1}$ before the vertices of $M_{2}$ in $\pi_{b}$ in the same
order as in $\pi_{b}^{*}$. The graph induced by $V_{b}^{1}$ and $V_{t}$ is the
same graph as $G$, hence it has at most $M$ crossings. Since $V_{t}$ only has
neighbors in $V_{b}$ and all those neighbors are in $V_{b}^{1}$, it has no
other outgoing edges, similarly, all edges incident to vertices in $W_{t}$ are
assigned to the copies in $V_{b}^{2}$. The remaining graph is crossing-free as
the vertices in $U_{t}$ and $W_{t}$ form a crossing-free matching with the
vertices in $U_{b}$ and $V_{b}^{2}$.

Conversely, let $G^{*}$ be a 2-layer drawing obtained from $G^{\prime}$ after
$k$ split operations that has at most $M$ crossings. Since each vertex $v\in
V_{b}$ has a neighbor $w\in W_{t}$, it induces $M+1$ crossings with edges
induced by the vertices in $U_{t}\cup U_{b}$. Since the vertices in $U_{b}$
have a single neighbor, they cannot be split, thus every vertex in $V_{b}$ is
split once, and their neighborhood are partitioned for each copy in the
following way: one copy receives the neighbor in $W_{t}$ and one copy receives
the remaining neighbors, which are in $V_{t}$ (Figure 2(b)), thus avoiding the
at least $M+1$ crossings induced by $U_{t}\cup U_{b}$. Any other split would
imply at least $M+1$ crossings. The graph induced by the copies that receive
the neighbors in $V_{t}$ has at most $M$ crossings, thus, the ordering found
for those copies is a solution to the DCP instance $G$.

(a) Instance of CMS($k$) constructed from a DCP instance, in light gray the
vertices in $U_{t}\cup U_{b}$; before splitting.

(b) After splitting.

(c) Vertex $v_{i}$ with span 6 and a split in $V^{l}$ (span 1) and $V^{r}$
(span 3). The barycenter of $V^{r}$ is $p^{r}$. When moving right from $p_{i}$
in CR-count we process $v_{i+1}$ (reduces $|V^{r}|$ crossings) and $v_{i+2}$
(reduces $|V^{r}|$ but adds 1 crossing), but not $v_{i+3}$.

Figure 2: Illustrations for Theorem 5.1 (a)–(b); illustration for the crossing
reduction heuristics (c).

Next, we present a simple -time algorithm for the crossing minimization
version of CMS(,) parameterized by the number $k$ of splits, i.e., the
algorithm runs in polynomial time $O(n^{f(k)})$, where $n$ is the input size,
$k$ is the parameter, and $f$ is a computable function. Let $G=(V_{t}\cup
V_{b},E)$ be a 2-layer graph with vertex orders $\pi_{t}$ and $\pi_{b}$ and
let $k$ be the desired number of splits. Our algorithm executes the following
steps. First, it determines a set of splits by choosing $k$ times a vertex
from the $n$ vertices in $V_{b}$ – we enumerate all options. For any vertex
$v\in V_{b}$ split $i$ times in the first step, $v$ is replaced by the set of
copies $\\{v_{1},...,v_{i+1}\\}$. The neighborhood $N(v)$ of a vertex $v\in
V_{b}$ is a subset of $V_{t}$ ordered by $\pi_{t}$. We partition this ordered
neighborhood into $i+1$ consecutive subsets, i.e., for each subset, all its
elements are sequential in $N(v)$ – again, we enumerate all possible
partitions. Each set is assigned to be the neighborhood of one of the copies
of $v$. The algorithm then chooses an ordering of all copies of all split
vertices and attempts all their possible placements by merging them into the
order $\pi_{b}$ of the unsplit vertices of $V_{b}$. The crossing number of
every resulting layout is computed and the graph with minimum crossing number
yields the solution to our input. It remains to show that the running time of
this algorithm is polynomial for constant $k$.

######  Theorem 5.3.

For a 2-layer graph $G=(V_{t}\cup V_{b},E)$ with vertex orders
$\pi_{t},\pi_{b}$ and a constant $k\in\mathbb{N}$ we can minimize the number
of crossings by applying at most $k$ splits in time $O(n^{4k})$.

######  Proof 5.4.

Let $G^{*}$ be a crossing-minimal solution after applying $k$ splits on
$V_{b}$ and let us assume that our algorithm would not find a solution with
this number of crossings. As our algorithm considers all possibilities to
apply $k$ splits, it also attempts the splits applied in $G^{*}$. Similarly,
the neighborhood partition of $G^{*}$ and the copy placement are explicitly
considered by the algorithm as it enumerates all possibilities. Hence a
solution at least as good as $G^{*}$ is found, proving correctness.

Let $n_{t}=|V_{t}|$ and $n_{b}=|V_{b}|$ with $n=n_{t}+n_{b}$. The algorithm
initially chooses $k$ times from $n_{b}$ vertices leading to $n_{b}^{k}$
possible sets of copies. Since a vertex has degree at most $n_{t}$, there are
at most $n_{t}^{k}$ possible neighborhoods for each copy. Additionally, there
are $(2k)!$ orderings of at most $2k$ copies. Lastly, there are $n_{b}^{2k}$
possible placement of the $2k$ ordered copies between the at most $n_{b}$
unsplit vertices in $\pi_{b}$. This leads to an overall runtime of
$O((2k)!\cdot n^{4k})=O(n^{4k})$ to iterate through all possible solutions and
select the one with a minimum number of crossings.

##  6 Crossing Reduction Heuristics

In this section we present two greedy heuristics to iteratively reduce
crossings in a two-layer drawing by selecting and splitting vertices; see
Algorithms 3–4 in the supplemental material for the pseudocode. The input to
the algorithm is a bipartite graph $G=(V_{t}\cup V_{b},E)$, order $\pi_{t}$ of
$V_{t}$ and order $\pi_{b}$ of $V_{b}$. Here we use the barycenter heuristic
for the initial orders, but any initial order computed by a crossing-reduction
algorithm can also be used. Additionally, an input parameter $k$ is specified
that represents a budget of available split operations. For both heuristics we
iteratively perform $k$ splits by selecting the most promising vertex in
$V_{b}$ and a partition of its respective neighbors in $V_{t}$ into a
consecutive set of left neighbors $V^{l}$ and a consecutive set of right
neighbors $V^{r}$. After splitting, the original vertex receives the set
$V^{l}$ assigned as neighbors and the copy receives the set $V^{r}$. Next we
describe how the vertex to be split is selected in each of the heuristics.

Firstly, in the case of the max-span heuristic we select the vertex $v$ with
the maximum _span_ , i.e., the maximum distance between its leftmost neighbor
and rightmost neighbor in $\pi_{t}$. Then, we process $v$ by iterating in
order over its neighbors and assigning them to either the set of left
neighbors $V^{l}$ or right neighbors $V^{r}$ depending on the index; see Fig.
2(c). In each iteration we compute the sum of the squared span of $V^{l}$ and
$V^{r}$. The minimum value indicates the best partition of $v$’s neighbors.
The complexity of the heuristic is linear in the number of edges $O(|E|)$.

Secondly, the CR-count heuristic selects promising split vertices by computing
crossings that can be reduced and selects the vertex with potentially most
reduced crossings. First, we assign each vertex $v_{i}$ in $V_{b}$ a position
$p_{i}\in\mathbb{R}$ which is the barycenter of positions in $\pi_{t}$ of its
neighbors in $V_{t}$. Similarly to max-span, we iterate in order over the
neighbors of all $v_{i}$ creating partitions $V^{l}$ and $V^{r}$. In each
iteration we compute the barycenter $p^{l}$ of $V^{l}$ and $p^{r}$ of $V^{r}$;
see Figure 2(c). Next, we start from position $p_{i}$ and move in ascending
order processing all other vertices in $V_{b}$ until we reach $p^{r}$. To
process a vertex $v_{j}\in V_{b}$ we look at all edges to its neighbors
$N(v_{j})\subseteq V_{t}$ and use a case distinction to count how many
crossings can be reduced. In the first case a neighbor in $V_{t}$ is left of
the leftmost vertex in $V^{r}$. Here, we would reduce $|V^{r}|$ crossings as
the new position of $v_{r}$ would not cross. In the second case a neighbor is
between the leftmost and rightmost vertex in $V^{r}$, i.e., we would reduce
some crossings but add others. In the third case a neighbor is right of the
rightmost vertex in $V^{r}$, i.e., no crossings can be reduced. Likewise, we
process vertices to the left of $v_{i}$ up to the barycenter $p^{l}$. Finally,
after computing all potentially reducible crossings for each vertex and split
combination, we select the combination reducing the crossings most, assign
$V_{l}$ to the original vertex and $V_{r}$ to the new copy. Both vertices are
positioned in their respective barycenters $p^{l}$ and $p^{r}$ in the order.
The complexity of the algorithm is $O(|V_{b}|^{2}|V_{t}|)$.

Algorithm 3 max-span heuristic

$G=(V_{t}\cup V_{b},E)$, $\pi_{t}$, $\pi_{b}$, $k$

$G^{\prime}$, $V^{\prime}_{b}$, $\pi_{b}^{\prime}$

$G^{\prime}\leftarrow G$

$V^{\prime}_{b}\leftarrow V_{b}$

$\pi_{b}^{\prime}\leftarrow\pi_{b}$

while $k>0$ do

$maxSpan\leftarrow 0$

$splitNode\leftarrow None$

for $i=1,\cdots,|V^{\prime}_{b}|$ do

// compute index of leftmost/rightmost neighbor of $v_{i}$ in $\pi_{t}$

$minNeighbor\leftarrow\text{leftmostNeighbor}(v_{i},N(v_{i}),\pi_{t})$

$maxNeighbor\leftarrow\text{rightmostNeighbor}(v_{i},N(v_{i}),\pi_{t})$

$span\leftarrow maxNeighbor-minNeighbor$

if $span>maxSpan$ then

$maxSpan\leftarrow span$

$splitNode\leftarrow v_{i}$

end if

end for

if $maxSpan==0$ then // no split possible

return $G,V^{\prime}_{b},\pi^{\prime}_{b}$

else

$N^{o}\leftarrow orderByIndex(N(splitNode),\pi_{t})$

$V^{l}\leftarrow\emptyset$

$V^{r}\leftarrow N^{o}$

$minSpan\leftarrow(\text{computeSpan}(V^{r},\pi_{t}))^{2}$

$V^{l}_{s}\leftarrow V^{l}$

$V^{r}_{s}\leftarrow V^{r}$

for $i=1,\dots,|N^{o}|$ do

$V^{l}\leftarrow V^{l}\cup\\{v_{i}\\}$

$V^{r}\leftarrow V^{r}\setminus\\{v_{i}\\}$

$span\leftarrow(\text{computeSpan}(V^{l},\pi_{t}))^{2}+(\text{computeSpan}(V^{r},\pi_{t}))^{2}$

if $span<minSpan$ then

$minSpan\leftarrow span$

$V^{l}_{s}\leftarrow V^{l}$

$V^{r}_{s}\leftarrow V^{r}$

end if

end for

// update $G$ and $\pi_{b}$ by removing $v_{i}$ and adding $v_{l}$ and $v_{r}$
with neighbors $V^{l}_{s}$ and $V^{r}_{s}$

// $v_{l}$ and $v_{r}$ get the placed in the barycenter of $V^{l}_{s}$ and
$V^{r}_{s}$ in the order $\pi^{\prime}_{b}$

$\text{updateGraphAndOrder}(G^{\prime},V^{\prime}_{b},\pi^{\prime}_{b},V^{l}_{s},V^{r}_{s})$

end if

$k\leftarrow k-1$

end while

return $G,V^{\prime}_{b},\pi_{b}$

Algorithm 4 CR-count heuristic

$G=(V_{t}\cup V_{b},E)$, $\pi_{t}$, $\pi_{b}$, $k$

$G^{\prime}$, $V^{\prime}_{b}$, $\pi_{b}^{\prime}$

$G^{\prime}\leftarrow G$

$V^{\prime}_{b}\leftarrow V_{b}$

$\pi_{b}^{\prime}\leftarrow\pi_{b}$

while $k>0$ do

$V^{l}_{s}\leftarrow\emptyset$

$V^{r}_{s}\leftarrow\emptyset$

$bestSplit\leftarrow 0$

for $i=1,\dots,|V_{b}^{\prime}|$ do

$N^{o}\leftarrow orderByIndex(N(splitNode),\pi_{t})$

$V^{l}\leftarrow\emptyset$

$V^{r}\leftarrow N^{o}$

$p_{i}\leftarrow\text{computeBarycenter}(G,N^{o},\pi_{t})$

for $j=1,\dots,|N^{o}|$ do

$V^{l}\leftarrow V^{l}\cup\\{v_{j}\\}$

$V^{r}\leftarrow V^{r}\setminus\\{v_{j}\\}$

$p^{l}\leftarrow\text{computeBarycenter}(G,V^{l},\pi_{t})$

$p^{r}\leftarrow\text{computeBarycenter}(G,V^{r},\pi_{t})$

// count avoidable crossings in a range, i.e. between $p_{i}$ and $p^{r}$

$count^{l}\leftarrow\text{countCrossingsInRange}(G,\pi_{t},\pi^{\prime}_{b},p^{l},p_{i})$

$count^{r}\leftarrow\text{countCrossingsInRange}(G,\pi_{t},\pi^{\prime}_{b},p_{i},p^{r})$

if $bestSplit<count^{l}+count^{r}$ then

$bestSplit\leftarrow count^{l}+count^{r}$

$V^{l}_{s}\leftarrow V^{l}$

$V^{r}_{s}\leftarrow V^{r}$

end if

end for

end for

if $bestSplit==0$ then // no split possible

return $G,V^{\prime}_{b},\pi^{\prime}_{b}$

else

// update $G$ and $\pi_{b}$ by removing $v_{i}$ and adding $v_{l}$ and $v_{r}$
with neighbors $V^{l}_{s}$ and $V^{r}_{s}$

// $v_{l}$ and $v_{r}$ get the placed in the barycenter of $V^{l}_{s}$ and
$V^{r}_{s}$ in the order $\pi^{\prime}_{b}$

$\text{updateGraphAndOrder}(G^{\prime},V^{\prime}_{b},\pi^{\prime}_{b},V^{l}_{s},V^{r}_{s})$

end if

$k\leftarrow k-1$

end while

return $G,V^{\prime}_{b},\pi_{b}$

##  7 Experimental Results

We have experimentally evaluated four of the five algorithms described earlier
with 22 real-world datasets: the exact algorithm of CRS($k$) with Fixed Order,
the exact algorithm of CRSV($k$) with Fixed Order, and two heuristics for
crossing reduction. The algorithm behind Thm. 5.3 is inefficient in practice.
We analyze performance w.r.t. the number of crossings in the layouts, number
of vertex splits, number of vertices that we split, the maximum number of
splits, and running time.

###  7.1 Experimental Design

We have mentioned that 2-layer drawings have been applied in visualizing
graphs defined on anatomical structures and cell types in the human body [1].
There exists a variety of cell types, genes, and proteins related to different
organs of the human body. Hierarchical structures have been used to show the
relationship between organs to anatomical structures, anatomical structures to
cell types, and cell types to genes/proteins. Cell types and genes/proteins
situate on a particular layer, unlike anatomical structures. Hence, we can
consider a 2-layer graph $G$ where cell types represent one layer and
genes/proteins represent another layer and analyze $G$ before and after
splitting. In this section, we consider the real-world 2-layer graphs
generated from the dataset of different organs and show the experimental
results obtained on those graphs.

###  7.2 Datasets

We use 22 real-world instances of 2-layer graphs from [1]; see Table 1.

Organ | $|V|$ | $|E|$ | Cell types | Genes/proteins | Density | Max degree
---|---|---|---|---|---|---
Blood | 179 | 461 | 30 | 149 | 0.0289 | 57
Fallopian Tube | 42 | 32 | 19 | 23 | 0.0371 | 3
Lung | 231 | 231 | 69 | 162 | 0.008 | 8
Peripheral Nervous System | 3 | 2 | 1 | 2 | 0.666 | 2
Thymus | 552 | 658 | 41 | 511 | 0.00432 | 93
Heart | 60 | 51 | 15 | 45 | 0.028 | 7
Lymph Nodes | 299 | 491 | 44 | 255 | 0.0110 | 36
Prostate | 43 | 36 | 12 | 31 | 0.039 | 3
Ureter | 44 | 53 | 14 | 30 | 0.0560 | 9
Bone Marrow | 343 | 662 | 45 | 298 | 0.011 | 25
Kidney | 201 | 237 | 58 | 143 | 0.011 | 8
Skin | 102 | 90 | 36 | 66 | 0.017 | 7
Urinary Bladder | 46 | 55 | 15 | 31 | 0.053 | 9
Brain | 381 | 346 | 127 | 254 | 0.004 | 5
Large Intestine | 124 | 139 | 51 | 73 | 0.0182 | 8
Ovary | 9 | 6 | 3 | 6 | 0.166 | 2
Small Intestine | 18 | 13 | 5 | 13 | 0.084 | 4
Uterus | 61 | 65 | 16 | 45 | 0.035 | 9
Eye | 145 | 270 | 47 | 98 | 0.0258 | 68
Liver | 73 | 57 | 26 | 47 | 0.0216 | 5
Pancreas | 69 | 100 | 29 | 40 | 0.042 | 12
Spleen | 290 | 414 | 65 | 225 | 0.009 | 23
Table 1: Statistics about the organ graphs from the HubMAP dataset [1]. The
density of a graph $G=(V,E)$ with $V=V_{t}\cup V_{b}$ is defined as
$2|E|/(|V|(|V|-1))$.

###  7.3 Interactive Tool Design

We developed an interactive tool, where the user can upload a dataset and
visualize the corresponding 2-layer graph; see Fig. 5. A dataset can be loaded
by pasting JSON-formatted text in the input area on the left-hand side of the
interface. We use blue and red colors to draw nodes that represent cell types
and genes/proteins respectively. There is a legend in the top left corner of
the interface to describe the color code. Instead of using top and bottom
layers, we use left and right layers, for easier node labeling (i.e., the left
and right layers represent $V_{t}$ and $V_{b}$). There are multiple radio
buttons to the configuration of the drawing. The user can fix the order of
either the blue vertices or the red vertices by selecting one set of radio
buttons. The number of vertex splits depends on the initial layout. We
consider two types of initial layouts: the vertices in each layer are
positioned in alphabetical order, or in barycentric order [24]. The user can
select an initial order from the input interface by using another set of radio
buttons. There are “Draw” and “Split” buttons in the interface. Once the user
selects an order for the left layer and clicks the draw button, then the
initial ordered layout will be shown on the right side of the interface.
Clicking the split button replaces the initial layout and shows the final
layout on the right side of the interface.

The right output interface is interactive; the user can see further details
using different interactions. When the graph is large the user can scroll up
and down to see different parts of the layout. The user can highlight the
adjacent edges by clicking on a particular vertex in case of dense layouts. We
keep the label texts less than or equal to ten characters. If a label is
longer then we show the first ten characters and truncate the rest. If the
user puts the mouse over the label or the corresponding vertex, a pop-up
message will show the full label. If the user moves out the mouse, the message
will be removed too. Besides showing the full label, we also provide other
useful information, e.g., the degree and ID of the vertex; see Figure 3.

(a) The system highlights the adjacent edges when the user clicks on a vertex
(“basophil” in this case).

(b) A pop-up message showing the full label, and other related information.

Figure 3: Interacting with the system.

Figure 4: Showing the running time w.r.t. the number of edges. The vertices
$V_{t}$ are the cell types and the vertices $V_{b}$ are the genes/proteins.
The vertices are alphabetically ordered. This is corresponding to the exact
algorithm of CRS($k$) with Fixed Order. We can see as the number of edges
increase the running time increases as expected.

(a) The input layout on the right side appears after inserting the dataset
into the text area and clicking the draw button.

(b) The output layout appears on the right side after clicking the split
button.

Figure 5: The user interface. Datasets of the human body [1] can be uploaded,
processed with the presented algorithms, and visualized.

###  7.4 Evaluation Results

We first evaluate the exact algorithms for CRS($k$) and CRSV($k$) with Fixed
Order. We have run experiments on 22 organ graphs on four settings: (1) the
blue vertices (cell type) are fixed and the initial layout is generated using
alphabetical order, (2) the red vertices (gene/protein) are fixed and the
initial layout is generated using alphabetical order, (3) the blue vertices
are fixed and initial layout is generated using barycentric heuristic, and (4)
the red vertices are fixed and initial layout is generated using the
barycentric heuristic. For each setting, we provide the initial number of
crossings, number of vertices in the top (or left) layers that have fixed
order, the number of bottom (or right) vertices, the number of splits, the
number of split vertices, and the maximum number of splits; see Tables 2–5 in
the supplemental material. The number of crossings in the initial layouts
generated from alphabetical order is 2.7 times larger in total than in layouts
generated by the barycentric heuristic. The number of splits is 1.58 times
larger in total when we fix the gene/protein vertices (Tables 3 and 5). Note
that for all organ graphs, the number of gene/protein vertices is relatively
larger compared to the cell type vertices. When the cell-type vertices are
fixed, there is more flexibility for splitting. Hence the numbers of splits in
Tables 2 and 4 are smaller than in Tables 3 and 5. Similarly, the maximum
number of splits is 2.5 times larger in total when the gene/protein vertices
are fixed.

Organ | Crossings |  $|V_{t}|$ |  $|V_{b}|$ | CRS($k$) with Fixed Order | CRSV($k$) with Fixed Order
---|---|---|---|---|---
Splits |  Split vertices |  Max splits |  Time (ms) | Splits |  Split vertices |  Max splits |  Time (ms)
Bone Marrow | 111440 |  45 |  298 | 343 |  136 |  16 |  1.5 | 343 |  134 |  17 |  1.5
Brain | 28345 |  127 |  254 | 78 |  63 |  4 |  2.9 | 78 |  63 |  4 |  2.9
Heart | 504 |  15 |  45 | 6 |  6 |  1 |  0.3 | 6 |  6 |  1 |  0.4
Kidney | 13347 |  58 |  143 | 85 |  52 |  4 |  1.5 | 85 |  52 |  4 |  1.5
Large intestine | 4778 |  51 |  73 | 58 |  25 |  6 |  0.5 | 59 |  24 |  6 |  0.6
Lung | 11654 |  69 |  162 | 63 |  39 |  6 |  0.9 | 63 |  39 |  6 |  0.9
Lymph nodes | 59709 |  44 |  255 | 213 |  100 |  10 |  1.0 | 213 |  100 |  10 |  1.0
Skin | 2066 |  36 |  66 | 19 |  11 |  3 |  0.5 | 19 |  11 |  3 |  0.4
Spleen | 40565 |  65 |  225 | 165 |  75 |  10 |  1.3 | 166 |  75 |  11 |  1.4
Thymus | 102067 |  41 |  511 | 135 |  100 |  5 |  1.8 | 135 |  100 |  5 |  1.8
Eye | 17046 |  47 |  98 | 164 |  78 |  5 |  0.8 | 166 |  78 |  5 |  0.9
Fallopian Tube | 153 |  19 |  23 | 6 |  5 |  2 |  0.4 | 6 |  5 |  2 |  0.4
Liver | 625 |  26 |  47 | 9 |  8 |  2 |  0.5 | 9 |  8 |  2 |  0.5
Pancreas | 2510 |  29 |  40 | 56 |  32 |  6 |  0.5 | 56 |  32 |  6 |  0.6
Peripheral Nervous System | 0 |  1 |  2 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Prostate | 405 |  12 |  31 | 3 |  3 |  1 |  0.3 | 3 |  3 |  1 |  0.3
Ovary | 8 |  3 |  6 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Small Intestine | 28 |  5 |  13 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Ureter | 512 |  14 |  30 | 21 |  19 |  2 |  0.3 | 21 |  19 |  2 |  0.4
Urinary Bladder | 628 |  15 |  31 | 21 |  21 |  1 |  1.1 | 21 |  21 |  1 |  1.1
Uterus | 1147 |  16 |  45 | 20 |  12 |  4 |  0.2 | 20 |  12 |  4 |  0.2
Blood | 49071 |  30 |  149 | 288 |  131 |  11 |  1.2 | 290 |  131 |  14 |  1.3
Table 2: The vertices $V_{t}$ are the cell types and the vertices $V_{b}$ are the genes/proteins. The vertices are alphabetically ordered. Organ | Crossings |  $|V_{t}|$ |  $|V_{b}|$ | CRS($k$) with Fixed Order | CRSV($k$) with Fixed Order
---|---|---|---|---|---
Splits |  Split vertices |  Max splits |  Time (ms) | Splits |  Split vertices |  Max splits |  Time (ms)
Bone Marrow | 111440 |  298 |  45 | 569 |  45 |  22 |  1.7 | 569 |  45 |  22 |  1.6
Brain | 28345 |  254 |  127 | 214 |  124 |  4 |  3.1 | 214 |  124 |  4 |  3.1
Heart | 504 |  45 |  15 | 30 |  14 |  4 |  0.3 | 30 |  14 |  4 |  0.3
Kidney | 13347 |  143 |  58 | 164 |  56 |  7 |  1.4 | 164 |  56 |  7 |  1.3
Large intestine | 4778 |  73 |  51 | 76 |  32 |  6 |  0.5 | 76 |  32 |  6 |  0.4
Lung | 11654 |  162 |  69 | 151 |  64 |  4 |  1.1 | 151 |  64 |  4 |  1.1
Lymph nodes | 59709 |  255 |  44 | 378 |  42 |  26 |  1.0 | 379 |  42 |  27 |  0.9
Skin | 2066 |  66 |  36 | 48 |  32 |  2 |  0.6 | 48 |  32 |  2 |  0.6
Spleen | 40565 |  225 |  65 | 311 |  58 |  20 |  1.5 | 312 |  58 |  19 |  1.5
Thymus | 102067 |  511 |  41 | 514 |  36 |  69 |  2.1 | 514 |  36 |  69 |  2.1
Eye | 17046 |  98 |  47 | 172 |  29 |  40 |  0.9 | 179 |  29 |  37 |  0.9
Fallopian Tube | 153 |  23 |  19 | 12 |  8 |  2 |  0.5 | 12 |  8 |  2 |  0.5
Liver | 625 |  47 |  26 | 27 |  12 |  4 |  0.7 | 27 |  12 |  4 |  0.6
Pancreas | 2510 |  40 |  29 | 53 |  22 |  7 |  0.6 | 53 |  22 |  7 |  0.6
Peripheral Nervous System | 0 |  2 |  1 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Prostate | 405 |  31 |  12 | 20 |  12 |  2 |  0.3 | 20 |  12 |  2 |  0.3
Ovary | 8 |  6 |  3 | 3 |  3 |  1 |  0.1 | 3 |  3 |  1 |  0.1
Small Intestine | 28 |  13 |  5 | 7 |  3 |  3 |  0.1 | 7 |  3 |  3 |  0.1
Ureter | 512 |  30 |  14 | 28 |  13 |  6 |  0.5 | 28 |  13 |  6 |  0.5
Urinary Bladder | 628 |  31 |  15 | 30 |  14 |  5 |  1.1 | 30 |  14 |  5 |  1.2
Uterus | 1147 |  45 |  16 | 44 |  16 |  6 |  0.2 | 44 |  16 |  6 |  0.2
Blood | 49071 |  149 |  30 | 379 |  30 |  40 |  1.4 | 379 |  30 |  40 |  1.4
Table 3: The vertices $V_{t}$ are the genes/proteins and the vertices $V_{b}$ are the cell types. The vertices are alphabetically ordered. Organ | Crossings |  $|V_{t}|$ |  $|V_{b}|$ | CRS($k$) with Fixed Order | CRSV($k$) with Fixed Order
---|---|---|---|---|---
Splits |  Split vertices |  Max splits |  Time (ms) | Splits |  Split vertices |  Max splits |  Time (ms)
Bone Marrow | 32599 |  45 |  298 | 323 |  130 |  17 |  1.5 | 323 |  124 |  17 |  1.6
Brain | 4773 |  127 |  254 | 71 |  60 |  3 |  3.2 | 72 |  59 |  3 |  3.1
Heart | 211 |  15 |  45 | 6 |  6 |  1 |  0.4 | 6 |  6 |  1 |  0.3
Kidney | 1207 |  58 |  143 | 69 |  46 |  4 |  1.4 | 70 |  45 |  4 |  1.5
Large intestine | 1878 |  51 |  73 | 49 |  25 |  6 |  0.7 | 50 |  24 |  7 |  0.6
Lung | 1970 |  69 |  162 | 64 |  37 |  7 |  1.3 | 64 |  37 |  7 |  1.2
Lymph nodes | 33315 |  44 |  255 | 214 |  104 |  10 |  1.3 | 216 |  104 |  10 |  1.2
Skin | 339 |  36 |  66 | 14 |  9 |  3 |  0.8 | 14 |  9 |  3 |  0.7
Spleen | 24833 |  65 |  225 | 171 |  76 |  9 |  1.7 | 172 |  75 |  9 |  1.8
Thymus | 34863 |  41 |  511 | 136 |  102 |  5 |  2.3 | 137 |  101 |  5 |  2.4
Eye | 8576 |  47 |  98 | 154 |  73 |  5 |  1.1 | 155 |  72 |  5 |  1.2
Fallopian Tube | 47 |  19 |  23 | 7 |  7 |  1 |  0.7 | 7 |  7 |  1 |  0.6
Liver | 84 |  26 |  47 | 8 |  7 |  2 |  0.9 | 8 |  7 |  2 |  0.9
Pancreas | 925 |  29 |  40 | 46 |  29 |  5 |  0.8 | 46 |  29 |  5 |  0.7
Peripheral Nervous System | 0 |  1 |  2 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Prostate | 64 |  12 |  31 | 3 |  3 |  1 |  0.4 | 3 |  3 |  1 |  0.4
Ovary | 0 |  3 |  6 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Small Intestine | 0 |  5 |  13 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Ureter | 126 |  14 |  30 | 18 |  18 |  1 |  0.6 | 18 |  18 |  1 |  0.7
Urinary Bladder | 151 |  15 |  31 | 18 |  18 |  1 |  1.3 | 18 |  18 |  1 |  1.3
Uterus | 135 |  16 |  45 | 13 |  10 |  3 |  0.3 | 14 |  10 |  3 |  0.3
Blood | 19308 |  30 |  149 | 284 |  130 |  13 |  1.7 | 284 |  130 |  13 |  1.6
Table 4: The vertices $V_{t}$ are the cell types and the vertices $V_{b}$ are the genes/proteins. The vertices are ordered by repeatedly applying the barycentric heuristic on both sides. Organ | Crossings |  $|V_{t}|$ |  $|V_{b}|$ | CRS($k$) with Fixed Order | CRSV($k$) with Fixed Order
---|---|---|---|---|---
Splits |  Split vertices |  Max splits |  Time (ms) | Splits |  Split vertices |  Max splits |  Time (ms)
Bone Marrow | 32599 |  298 |  45 | 412 |  45 |  15 |  1.8 | 412 |  45 |  14 |  1.7
Brain | 4773 |  254 |  127 | 86 |  78 |  3 |  3.2 | 86 |  70 |  3 |  3.2
Heart | 211 |  45 |  15 | 16 |  11 |  3 |  0.4 | 16 |  11 |  3 |  0.4
Kidney | 1207 |  143 |  58 | 94 |  49 |  5 |  1.5 | 94 |  47 |  4 |  1.5
Large intestine | 1878 |  73 |  51 | 47 |  24 |  5 |  0.8 | 50 |  24 |  5 |  0.7
Lung | 1970 |  162 |  69 | 74 |  49 |  3 |  1.3 | 74 |  47 |  3 |  1.3
Lymph nodes | 33315 |  255 |  44 | 298 |  41 |  24 |  1.4 | 299 |  41 |  23 |  1.3
Skin | 339 |  66 |  36 | 22 |  19 |  2 |  0.8 | 22 |  19 |  2 |  0.8
Spleen | 24833 |  225 |  65 | 223 |  59 |  14 |  1.8 | 227 |  59 |  15 |  1.8
Thymus | 34863 |  511 |  41 | 320 |  35 |  46 |  2.4 | 320 |  34 |  48 |  2.5
Eye | 8576 |  98 |  47 | 146 |  25 |  34 |  1.1 | 149 |  25 |  35 |  1.1
Fallopian Tube | 47 |  23 |  19 | 5 |  5 |  1 |  0.6 | 5 |  5 |  1 |  0.6
Liver | 84 |  47 |  26 | 3 |  7 |  2 |  1.1 | 3 |  7 |  2 |  1.0
Pancreas | 925 |  40 |  29 | 42 |  21 |  6 |  0.8 | 42 |  20 |  6 |  0.8
Peripheral Nervous System | 0 |  2 |  1 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Prostate | 64 |  31 |  12 | 13 |  12 |  2 |  0.5 | 13 |  12 |  2 |  0.4
Ovary | 0 |  6 |  3 | 0 |  0 |  0 |  0.1 | 0 |  0 |  0 |  0.1
Small Intestine | 0 |  13 |  5 | 3 |  3 |  1 |  0.1 | 3 |  3 |  1 |  0.1
Ureter | 126 |  30 |  14 | 18 |  13 |  4 |  0.7 | 18 |  9 |  4 |  0.7
Urinary Bladder | 151 |  31 |  15 | 19 |  14 |  4 |  1.4 | 19 |  14 |  4 |  1.3
Uterus | 135 |  45 |  16 | 23 |  13 |  4 |  0.3 | 25 |  13 |  4 |  0.4
Blood | 19308 |  149 |  30 | 300 |  30 |  31 |  1.8 | 300 |  30 |  31 |  1.7
Table 5: The vertices $V_{t}$ are the genes/proteins and the vertices $V_{b}$
are the cell types. The vertices are ordered by repeatedly applying the
barycentric heuristic on both sides. Figure 6: Part of the input layout of the
2-layer graph corresponding to the anatomical structure of blood computed by
the exact algorithm for CRS($k$) with Fixed Order. The graph is large, hence
we show a part of the layout. Figure 7: Part of the output layout of the
2-layer graph corresponding to the anatomical structure of blood computed by
the exact algorithm for CRS($k$) with Fixed Order.

(a) Input layout

(b) Output layout

(c) Zoomed in input layout

(d) Zoomed in output layout

Figure 8: Input and output layouts of the exact algorithm of CRS($k$) with
Fixed Order for Bone Marrow.

(a) Input layout

(b) Output layout

(c) Zoomed in input layout

(d) Zoomed in output layout

Figure 9: Input and output layouts of the exact algorithm of CRS($k$) with
Fixed Order for Brain.

(a) Input layout

(b) Output layout

(c) Zoomed in input layout

(d) Zoomed in output layout

Figure 10: Input and output layouts of the exact algorithm of CRS($k$) with
Fixed Order for Heart.

A second set of experiments was conducted on the same 22 organ graphs to
evaluate the crossing minimization heuristics. We set the maximum budget $k$
of splits to $200$ and computed the number of remaining crossings after each
split. Additionally, we measured wall clock time after each iteration. Figure
11 shows the number of crossings in regards to $k$ for one example graphs.
Examples of other graphs, as well as runtime plots can be found in the
supplemental material; see Fig. 6–11. For both algorithms we observed a
similar performance regarding crossing reduction. In some cases one algorithm
slightly outperformed the other, but no clear trend is visible in the data.
Intuitively, it seems that in the case of max-span the length of edges
correlates with the number of crossings. Furthermore, the number of crossings
declines steeply at the beginning and for some graphs nearly 30% of crossings
are removed by the first 10 splits.

The runtime experiments confirmed the asymptotic runtime analysis. max-span
outperforms CR-count on every datasets in regards to total runtime and
scalability.

(a)

(b)

Figure 11: max-span and CR-count heuristic applied to the eye dataset. Both
algorithms have nearly identical performance regarding crossing reduction as
seen in (a). However, max-span outperforms CR-count regarding runtime (b).

(a)

(b)

Figure 12: max-span and CR-count heuristic applied to the spleen dataset. Both
algorithms have nearly identical performance regarding crossing reduction as
seen in (a). However, max-span outperforms CR-count regarding runtime (b).

(a)

(b)

Figure 13: max-span and CR-count heuristic applied to the bone marrow dataset.
Both algorithms have nearly identical performance regarding crossing reduction
as seen in (a). However, max-span outperforms CR-count regarding runtime (b).

(a)

(b)

Figure 14: max-span and CR-count heuristic applied to the lymph nodes dataset.
Both algorithms have nearly identical performance regarding crossing reduction
as seen in (a). However, max-span outperforms CR-count regarding runtime (b).

(a)

(b)

Figure 15: max-span and CR-count heuristic applied to the lung nodes dataset.
Both algorithms have nearly identical performance regarding crossing reduction
as seen in (a). However, max-span outperforms CR-count regarding runtime (b).

(a)

(b)

Figure 16: max-span and CR-count heuristic applied to the pancrease nodes
dataset. Both algorithms have nearly identical performance regarding crossing
reduction as seen in (a). However, max-span outperforms CR-count regarding
runtime (b).

All codes for user interface, algorithms, experimental data, and analysis are
available on Github at https://github.com/abureyanahmed/split_graphs.

##  8 Open Problems

Minimizing the total number of splits, or the number of split vertices are
natural problems. Other variants include minimizing the maximum number of
splits per vertex and considering the case where splits are allowed in both
layers. Vertex splits can also be used to improve other quality measures of a
2-layer layout (besides crossings). When visualizing large bipartite graphs, a
natural goal is to arrange the vertices so that a small window can capture all
the neighbors of a given node, i.e., minimize the maximum distance between the
first and last neighbors of a top vertex in the order of the bottom vertices.

Since a great deal of vertex splitting can dramatically change the structure
of the graph, it is desirable to have a bound on the number of splits. Hence,
in our problems, we take a parameter $k$ that limits the number of splits. One
can also consider the problem of finding the minimum number of splits to
generate a planar graph. This is known as the Planar Split Thickness of Graphs
[10]. It remains an interesting future research direction to find the trade-
off between the number of splits and the number of crossings as the graph size
changes.

###  8.1 Acknowledgments.

This work started at Dagstuhl Seminar 21152 “Multi-Level Graph Representation
for Big Data Arising in Science Mapping”. We thank the organizers and
participants for the discussions, particularly C. Raftopoulou.

## References

  * [1] https://hubmapconsortium.github.io/ccf-asct-reporter/
  * [2] Ahmed, R., Kobourov, S.G., Kryven, M.: An FPT algorithm for bipartite vertex splitting. In: Angelini, P., von Hanxleden, R. (eds.) Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers. Lecture Notes in Computer Science, vol. 13764, pp. 261–268. Springer (2022). 10.1007/978-3-031-22203-0_19, https://doi.org/10.1007/978-3-031-22203-0_19
  * [3] Börner, K., Teichmann, S.A., Quardokus, E.M., Gee, J.C., Browne, K., Osumi-Sutherland, D., Herr, B.W., Bueckle, A., Paul, H., Haniffa, M., et al.: Anatomical structures, cell types and biomarkers of the human reference atlas. Nature cell biology 23(11), 1117–1128 (2021)
  * [4] 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)
  * [5] Demetrescu, C., Finocchi, I.: Removing cycles for minimizing crossings. JEA 6, 2 (2001)
  * [6] Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph drawing beyond planarity. ACM Computing Surveys 52(1), 4:1–4:37 (2019)
  * [7] Eades, P., McKay, B., Wormald, N.: On an edge crossing problem. In: ACSC ’86. pp. 327–334 (1986)
  * [8] 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)
  * [9] Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11(4), 379–403 (1994)
  * [10] 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)
  * [11] Faria, L., de Figueiredo, C.M.H., Mendonça, C.F.X.: Splitting number is NP-complete. DAM 108(1), 65–83 (2001)
  * [12] Hartsfield, N., Jackson, B., Ringel, G.: The splitting number of the complete graph. Graphs and Combinatorics 1(1), 311–329 (1985)
  * [13] Henry, N., Bezerianos, A., Fekete, J.D.: Improving the readability of clustered social networks using node duplication. IEEE Transactions on Visualization and Computer Graphics 14(6), 1317–1324 (2008)
  * [14] Jackson, B., Ringel, G.: The splitting number of complete bipartite graphs. Archiv der Mathematik 42(2), 178–184 (1984)
  * [15] Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. JGAA 1(1), 1–25 (1997)
  * [16] Knauer, K., Ueckerdt, T.: Three ways to cover a graph. DM 339(2), 745–758 (2016)
  * [17] Kobayashi, Y., Tamaki, H.: A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization. Algorithmica 72(3), 778–790 (2015)
  * [18] Liebers, A.: Planarizing graphs – a survey and annotated bibliography. JGAA 5(1), 1–74 (2001)
  * [19] McGee, F., Renoust, B., Archambault, D., Ghoniem, M., Kerren, A., Pinaud, B., Pohl, M., Otjacques, B., Melançon, G., von Landesberger, T.: Visual Analysis of Multilayer Networks. Morgan & Claypool (2021)
  * [20] Nielsen, S.S., Ostaszewski, M., McGee, F., Hoksza, D., Zorzan, S.: Machine learning to support the presentation of complex pathway graphs. IEEE/ACM transactions on computational biology and bioinformatics 18(3), 1130–1141 (2019)
  * [21] Pezzotti, N., Fekete, J.D., Höllt, T., Lelieveldt, B.P.F., Eisemann, E., Vilanova, A.: Multiscale visualization and exploration of large bipartite graphs. CGF 37(3), 549–560 (2018)
  * [22] Purchase, H.: Which aesthetic has the greatest effect on human understanding? In: Graph Drawing. vol. 97, pp. 248–261 (1997)
  * [23] Scornavacca, C., Zickmann, F., Huson, D.H.: Tanglegrams for rooted phylogenetic trees and networks. Bioinformatics 27(13), i248–i256 (2011)
  * [24] Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. TSMC 11(2), 109–125 (1981)


Further author information: (Send correspondence to R. Bowens-Rubin)
R.B.R.: E-mail<EMAIL_ADDRESS>
# Performance of Large-Format Deformable Mirrors Constructed with TNO Variable
Reluctance Actuators

Rachel Bowens-Rubina  Philip Hinza  Wouter Jonkerb  Stefan Kuiperb  Cesar
Lagunaa  and Matthew Maniscalcob aUC Santa Cruz  1156 High St  Santa Cruz CA
USA;
b TNO Technical Sciences  Delft  The Netherlands

###### Abstract

Advancements in making high-efficiency actuators are an enabling technology
for building the next generation of large-format deformable mirrors. The
Netherlands Organization for Applied Scientific Research (TNO) has developed a
new style of variable-reluctance actuator that requires approximately eighty
times less power to operate as compared to the traditional style of voice-coil
actuators. We present the performance results from laboratory testing of TNO’s
57-actuator large-format deformable mirror from measuring the influence
functions, linearity, hysteresis, natural shape flattening, actuator cross-
coupling, creep, repeatability, and actuator lifetime. We measure a linearity
of 99.4 $\pm$ 0.33% and hysteresis of 2.10 $\pm$ 0.23% over a stroke of 10
microns, indicating that this technology has strong potential for use in on-
sky adaptive secondary mirrors (ASMs). We summarize plans for future lab
prototypes and ASMs that will further demonstrate this technology.

###### keywords:

Adaptive Optics, Adaptive Secondary Mirrors, Large Format Deformable Mirrors

##  1 INTRODUCTION

Adaptive secondary mirrors have been used successfully at telescopes like the
Large Binocular Telescope [1], Magellan [2], the VLT Observatory [3], and the
MMT Observatory [4]. However, these adaptive secondary mirror systems are
complex because they incorporate hundreds of power intensive voice-coil
actuators that require a dedicated cooling system and capacitive sensors [5].
The mirror facesheet fabrication has also traditionally required the grinding
of a large piece of glass into a thin glass sheet that is flexible enough to
be shaped by the actuators.

The Netherlands Organization for Applied Scientific Research (TNO) has made
significant breakthroughs in large-format deformable mirror technology that
could enable adaptive secondary mirrors to become simpler and less costly. The
key advancement is a new style of hybrid variable reluctance actuator that is
80 times more efficient than traditional voice-coil actuators (TNO actuator
efficiency [6] = $40N/\sqrt{W}$; MMT and LBT actuator efficiency [7] =
$0.5N/\sqrt{W}$). The low required power offers a pathway to eliminate the
actuator cooling system, miniaturize the system, and pack the actuators at
higher density. TNO is also developing solutions that could simplify the
facesheet fabrication by starting with thin glass sheets and utilizing glass-
slumping techniques to form the shape.

While these mirrors show great potential to make advanced adaptive optics
systems accessible to a wide variety of observatories, they have yet to be
proven to the astronomical community. This paper presents laboratory testing
performed of TNO’s third deformable-mirror prototype (DM3) to explore the
properties of TNO’s large-format deformable mirror technology. We report the
results of this testing and outline the future steps towards deployment of
this technology on-sky.

##  2 TECHNOLOGY OVERVIEW

###  2.1 Design of the TNO DM3

The DM3 is the third prototype large-format deformable mirror from TNO (Figure
1). It was built for lab demonstration in 2016. The surface is round (⌀150mm)
and flat to within 15.5 um peak-to-valley when the applied actuator current is
zero. DM3 was built using 57 actuators of 18mm pitch (Figure 2).

The mirror is controlled through a 64 analog output from a Real Time Linux
environment. The output voltages are controlled using an RDA interface to
Matlab running on an office PC. The user can control the shape of the mirror’s
surface by setting the current applied to each actuator. The update rate of
this setup is 300Hz.

Figure 1:  DM3 at the UCSC Lab for Adaptive Optics. The third prototype large-
format deformable mirror from TNO (DM3) contains 57 variable reluctance
actuators.

Figure 2: TNO Variable Reluctance Actuators (Left) _The 18mm-pitch TNO
Actuator used in DM3._ (Right) _Actuator layout in DM3._ The actuators used
for the testing reported in this paper are labeled by number in the green
boxes. The other actuators are shown in the gray boxes, and the channels
unoccupied are shown in white.

###  2.2 TESTBENCH SETUP

The University of California Santa Cruz Lab for Adaptive Optics (UCSC-LAO)
began testing the TNO DM3 in January of 2020. The testbed at UCSC-LAO (Figure
3) utilizes a Zygo Interferometer run with Metropro Software to measure the
shape of the mirror’s surface to a precision of 0.6 nm. Additional Matlab code
is being developed by UCSC-LAO to streamline the process of characterizing the
actuator linearity, hysteresis, creep, cross-coupling, repeatability, Zernike
pattern replication, and lifetime using this testbench. A cold chamber and
orientation setup will be integrated for future environmental and gravity
testing.

---
Figure 3:  Large-Format Deformable Mirror Testbench at the UCSC Lab for
Adaptive Optics. The testbench utilizes a Zygo Interferometer with MetroPro
software to measure surface shape. A beam expander is used so that the
majority of the DM3 can be measured.

##  3 DM3 TESTING RESULTS

###  3.1 Influence Functions

The influence function of each actuator was measured using an individual
actuator poke test. A $+20mA$ current was applied in an automated measurement
sequence to displace each actuator one-by-one. The displacement of these pokes
corresponded to approximately 730nm peak-to-valley. Twenty-one actuators
responded to the positive current with a positive displacement, and thirty-six
actuators responded with a negative displacement.

An example of the influence function measured for Actuator 42 is shown in
Figure 4. The influence function was measured with the natural shape of the
mirror subtracted such that only the displacement is seen. The cross-section
of the influence function is plotted in Figure 5 with a Gaussian, Moffat, and
Cauchy function fit. While each of the three functions can approximate part of
the profile, a custom profile would need to be created to correctly fit the
actuator cross sections at both the center and tails.

---
Figure 4:  Example Influence Function: The influence function for Actuator 42
as measured on April 30th, 2020. An applied voltage of +20mA resulted in an
actuator displacement of 727nm. Images are scaled with the x-y axis in
millimeters and the color axis and z-displacement in nanometers.
---
Figure 5:  Influence Function Profile. A cross-section of the influence
function for Actuator 42 was used to determine a profile of best fit. A
Moffat, Cauchy, and Gaussian curve were fit to the inner 100 points of the
cross section. The Cauchy and Gaussian fit approximate the center well, but do
not approximate the width correctly. The Moffat fit can approximate the width
to higher precision, but cannot be used to determine the center value. A
custom profile is needed to match the greater shape of the cross section.

###  3.2 Natural-Shape Surface Flattening

The natural shape of the TNO DM3 mirror has a peak-to-valley that is 15.5 um
with a 2780nm RMS variation (within $\diameter$140mm). To bring the surface as
flat as possible, a set of currents that could bring the mirror surface to the
lowest RMS possible was determined using an iterative process. At each step,
an image was taken using the Zygo. The next desired position for the actuators
to reproduce in the iteration ($i$) was set to the negative of the last image
taken ($S_{i}$). The next set of currents ($F_{i}$) to produce the desired
shape ($S_{i}$) were calculated using the influence functions matrix ($P$)
through the Moore-Penrose inverse:

$F_{i}=(P^{T}P)^{-1}P^{T}S_{i}.$ (1)

The new currents from the iteration were then summed with the previous
currents applied to find the new values to be applied
($F=\sum_{1}^{i=n}F_{i}$).

On April 30th 2020, fifteen iterations of flattening were performed to
calculate the optimal flattening currents. The majority of the variation was
removed after five iterations. The flattest shape was found on iteration 14
which had an RMS = 27.7nm (within $\diameter$140mm) with a peak-to-valley of
469nm, demonstrating that it is possible to flatten the surface by two orders
of magnitude. Figure 6 shows the natural shape of the mirror alongside the
shape after this flattening.

The total current needed to hold this shape across the 57 actuators was
1967mA, averaging 34.5 $\pm$ 6.6mA per actuator. The required power was 189mW
(3.3 mW/actuator). Riccardi et al. (2003, Table 1) states the power required
for a correction to a similar wavefront error with the LBT ASM requires 190
mW/actuator. [7], leading to a nearly sixty factor gain in this comparison.
This estimate does not include the additional 3.8 W/actuator of power needed
at the LBT collocated electronics crate, which is located slightly further
from the mirror but still on the secondary structure.

---
Figure 6:  Natural-Shape Surface Flattening. (Left) _DM3 Natural Surface
Shape_. Unpowered, the shape of the TNO DM3 mirror surface has a peak-to-
valley that is 15500nm (RMS = 2780nm within ⌀140mm). (Right) _Surface Shape
after Applied Flattening_. After flattening, the surface shape was brought
down to 28nm RMS with a peak-to-valley of 469 nm. The colorbar is reported in
units of nanometers.

###  3.3 Zernike Mode Testing

To determine how close DM3 was able reproduce ideal Zernike shapes, the first
57 Zernike Modes were applied to DM3. The currents needed to reproduce the
Zernike modes were calculated using Equation 1, where $S_{i}$ was the shape of
each Zernike pattern. No iterations were used in trying to reproduce the
Zernike pattern. An example of the side-by-side comparison between DM3 and an
ideal Zernike pattern can be viewed in Figure 7 for mode 12. A movie of the
full test can be watched at the following youtube link:
https://youtu.be/dpTzO46zg2Y.

To determine if a trend existed between the Zernike order number and how well
the mirror could replicate the pattern, the reduced chi square was calculated
for each Zernike frame (Figure 8). Modes with a large reduced chi square value
could not be replicated to as high precision. Overall, the spherical modes
were reproduced the least well (4, 12, 24, 40) of any categorization of mode
type. There was not a significant trend between the value of the reduced chi
square and low or high order mode number.

---
Figure 7:  Example Zernike Mode: Zernike Mode 12. The ideal shape (top) is
presented with the approximated shape made by DM3 (bottom). A movie of the
full Zernike test data from applying modes 1 - 57 to DM3 can be found at the
following youtube link: https://youtu.be/dpTzO46zg2Y.
---
Figure 8:  Zernike Mode Test Reduced Chi Square. The reduced chi square of
each Zernike data frame was measured to determine how well each Zernike mode
could be reproduced. Four of the spikes in the reduced chi square plot
corresponded to the spherical Zernike modes (4, 12, 24, 40), indicating that
these shapes were not as precisely replicated as the non-spherical modes.

###  3.4 Actuator Cross-Coupling

The actuator cross-coupling was measured to quantify how the movement of one
actuator will affect its neighbor. The cross-coupling was measured using the
cross section of the influence functions from the center row and center column
of actuators (Figure 9). The center actuator (45) was used in both samples.

The cross sections were corrected for their positive/negative displacement
polarity and then normalized. Two measurements were taken per actuator along
the line that intersected the neighboring actuator’s peak. Using these twenty
measurements, we measure an actuator cross-coupling of 37.07 $\pm$ 0.93%.

---
Figure 9:  Actuator Cross-Coupling. Five actuators from the inner row (24, 28,
45, 57, and 53) and five actuators from the inner column (38, 42, 45, 14, and
10) were used to measure the actuator cross-coupling. The filled lines
represent the normalized cross section of the actuators included in the
actuator cross-coupling measurement. The black dots indicate the values of the
cross-coupling measurements. The dashed lines are the influence functions of
the actuators in the row or column not used for the cross-coupling
calculation.

###  3.5 Linearity

Linearity testing was performed using five actuators (12, 14, 42, 55, and 57).
These actuators were run through a fifteen-step current pattern using positive
and negative currents, spanning from 0 to +140mA or 0 to -140mA (Figure 10).
Although the negative and positive current runs were performed separately,
linearity fitting considered the tests jointly for each actuator. The
displacement was measured using the mean of the seven points nearest to the
actuator center.

The displacement data were fit for each actuator (Figure 11). The slopes of
the fit for each actuator were averaged to reveal a displacement of 39.66
$\pm$ 0.54 nm/mA. The linearity data for the five actuators is presented in
Figure 11 with the percent residuals. The percent residuals were calculated
using,

$Residual(\%)=100\left(\frac{Data-Fit}{Data}\right).$ (2)

The mean of the percent residuals across the five actuators was used to
quantify the actuator linearity. We measure the actuators to be linear to
99.4% $\pm$ 0.33% (nonlinear to 0.6% $\pm$ 0.33%). The nonlinearity is most
evident at small currents (within $\pm$20mA) where the actuators tend to
undershoot their predicted position.

Figure 10: Current Patterns Used in Testing. (Left) Linearity testing was
performed in fifteen steps with a positive and negative current pattern. The
positive and negative current runs were combined by actuator for linearity
fitting. (Right) Hysteresis runs were performed using forty steps across five
maximum current values. Each run was analysed separately.
---
Figure 11:  Linearity Results. Linearity testing was performed using five
actuators. Actuators 12, 14, 55, and 57 were wired with negative polarity but
are adjusted here to be corrected to positive polarity. The average actuator
displacement was 39.66 $\pm$ 0.54 nm/mA. Displacement was linear to within
99.4% $\pm$ 0.33%. A negative percent displacement occurs at small current
values, meaning the actuator undershot the expected position.

###  3.6 Hysteresis

Actuator displacement varies depending on the previous position of the
actuator. To quantify this, we measured the hysteresis using the definition:

$Hyst(\%)=100\left(\frac{|S3-S1|}{|S2-S4|}\right)$ (3)

where $S1$ and $S3$ are the displacements measured at an applied current of
zero and $S2$ and $S4$ are the displacements measured at the maximum and
minimum current applied.

Hysteresis testing was performed using three actuators (14, 42, and 57)
stepped through five independent hysteresis loops. Each loop was done in forty
steps between currents of $\pm$5mA, $\pm$10mA, $\pm$20mA, $\pm$60mA,
$\pm$120mA (Figure 10). Three of these tests occurred in the least linear
portions of the actuator displacement curves ($\pm$5mA, $\pm$10mA, $\pm$20mA)
and provide worse-case scenario measurements of the hysteresis. No measurement
exceeded a hysteresis value of 3.5%. The average percent hysteresis measured
across all fifteen trials was 2.10 $\pm$ 0.23% (Figure 12).

Figure 12: Hysteresis testing results. (Top) A linear fit was performed and
the residuals were plotted for each hysteresis run. The example for Actuator
42 for the 120mA run is shown here. (Bottom) The percent hysteresis was
measured in fifteen trials to be 2.10 $\pm$ 0.23%.

###  3.7 Repeatability

A repeatability test was run to verify the ability for the DM3 to return to
the same shape when applying the same set of currents from day to day. The
repeatability testing was performed by applying the flattening current set
calculated on April 30th 2020. Five measurements were taken across five days
starting from zero currents applied. Images were visually inspected and the
RMS was used to quantify the shape. The images passed visual inspection and
the RMS did not change to within the precision of the Zygo Interferometer
(0.6nm).

The same shape was applied after the mirror had been running for unmeasured
amounts of times. The RMS differences in these images were observed to
fluctuate by up to $\Delta RMS=33.5$ nm.

###  3.8 Creep

Creep testing was performed by applying a current pattern and holding it for
twelve hours. Similar to the repeatability testing, the creep testing was run
by applying the flattening current pattern found on April 30th 2020.
Measurements were taken with the applied pattern subtracted such that the Zygo
images were more sensitive to any deviations. The tests were repeated three
times.

The only measurable change came from an added tilt on the order of 1000nm that
was believed to be from a shift in the beam expander mounting. Although the
data cannot conclusively rule out creep as an issue to <1000nm RMS, there is
no evidence for significant creep.

###  3.9 Lifetime Testing

A demonstration to test the working lifetime of the actuators is in progress.
The 57 actuators were set to a 34Hz cycle going from -50% to +50% of the
maximum stroke. This scenario is a strong worst case for an actual ASM in
operation, where the changes in deflection for each cycle will be much lower.
Periodically, DM3 is imaged with the Zygo interferometer. At the time of
writing, each of the 57 actuators has seen over 110 million cycles with no
detectable change in performance.

##  4 CONCLUSIONS

###  4.1 Summary of Results

The key results from each test of the TNO DM3 are summarized in Table 1. The
values determined from the laboratory testing at UCSC-LAO of the TNO DM3 are
consistent with the values quoted by TNO. The TNO variable reluctance
actuators show a linearity and hysteresis value similar to the voice-coil
actuators currently used in on-sky adaptive secondary mirrors while exhibiting
over 5.5 times lower power consumption.

Table 1: Summary of DM3 Testing Results Section | Test | Takeaway
---|---|---
3.1 | Influence functions |  | The influence function center location can be approximated
---
with a Gaussian or Cauchy. The width can be approximated
using a Moffit fit.
3.2 |  | Natural Shape
---
Surface Flattening
| The surface was brought from RMS = 2778nm to RMS = 28nm
---
with an average current per actuator = 34.5 $\pm$ 6.6mA,
total power = 189mW.
3.3 | Zernike Mode |  | There is not a significant trend between mode number and pattern
---
replication. The spherical modes were the least well replicated.
3.4 | Actuator Cross-Coupling | Cross Coupling = 37.07 $\pm$ 0.93%
3.5 | Linearity |  | Average Displacement = 39.66 $\pm$ 0.54 nm/mA;
---
Linearity = 99.4% $\pm$ 0.33%
3.6 | Hysteresis | Hyst = 2.10 $\pm$ 0.23%
3.7 | Repeatability |  | Mirror shape is repeatable to below measurement precision
---
when mirror starts from rest;
3.8 | Creep |  | Measurements could not rule out creep $<$1000nm RMS, but
---
there is no indication of creep issues
3.9 | Lifetime |  | Over 110 million cycles have been completed
---
on each actuator with no change in performance

###  4.2 Technology Development Plan

TNO is in the process of constructing its first on-sky adaptive secondary
mirror for use in the UH-88 telescope located on Maunakea. This adaptive
secondary mirror has an aspherical convex shape that is ⌀63cm. It is
fabricated using 210 actuators from the 2020 generation that can accommodate
larger actuator spacing and be arranged in a circular grid. This system is
expected to be ready for lab testing in the summer of 2021 and be deployed in
the telescope in early 2022. More information about the UH-88 ASM can be found
in this conference’s proceedings at SPIE No. 1144852 Chun et. al. 2020.

TNO is developing two future lab-model prototypes for use at UCSC-LAO. By
December 2020, TNO will deliver the First Laboratory Adaptive Secondary
Holophote (FLASH) (Figure 13). FLASH has a flat surface of ⌀160mm. It is
constructed using 19 actuators from the 2020 version developed for the UH-88
ASM. The testing presented in this paper will be repeated to verify the
properties of the new actuators. Additional testing will also be performed to
explore the effects of temperature, gravity, and any unexplained behaviors
found in the UH-88 ASM.

Following the FLASH, the Second Laboratory Adaptive Secondary Holophote
(SLASH) will be constructed using an aspherical convex facesheet. The SLASH
will be ⌀370mm and contain 61 actuators from the next generation. While the
SLASH design is still being finalized, we are investigating the possibilities
of integrating this prototype into the UC Lick Observatory’s Automated Planet
Finder telescope as an adaptive secondary mirror. If this design is selected,
SLASH may become the first on-sky ASM to be paired with a precision radial
velocity instrument.

Both FLASH and SLASH will be constructed using thin facesheets formed using
glass slumping techniques. This glass slumping is done in-house at the UCSC-
LAO using flat borofloat sheets. The glass is heated in a glass kiln and let
sag into a fused silica mold over the course of several days. It is then
optically coated with aluminium to create a mirrored surface. UCSC-LAO has
produced the $\diameter$160mm flat facesheet for the FLASH using this
technique in order to promote the technology readiness level of this
fabrication approach. This technique will be developed to expand to meter
sizes, greatly reducing the costs associated with producing flexible glass
facesheets for use in ASMs for large telescopes.

Design studies are in progress to understand the feasibility and constraints
of building an adaptive secondary mirror for the UCO Lick Automated Planet
Finder Telescope and the W.M. Keck Observatory with TNO technology. More
information about these designs can be found in this conference’s proceedings
at SPIE No. 11448-233 Hinz et. al. 2020.

Figure 13: FLASH: the First Lab Adaptive Secondary Holophote. The 19-actuator FLASH will be the first large-format deformable mirror designed for use at the UCSC Lab for Adaptive Optics. It will be used to test the 2020 generation of actuators and explore unexplained behaviors in the UH-88 ASM. (Left) CAD model of the FLASH. (Right) FLASH in the process of being constructed at TNO.  Table 2:  TNO Deformable Mirrors Tested by UCSC-LAO |  | # of
---
Act.
| Diameter
---
(mm)
| Actuator
---
Type
Facesheet |  | Communication
---
interface
Status
DM3 | 57 | 150 |  | 2016 model
---
designed for
lab prototypes
| standard flat wafer
---
(no optical figuring);
thickness = 1 mm
Analog |  | Testing
---
results
reported
FLASH | 19 | 160 |  | 2020 model
---
designed for
UH-88
| Flat slumped glass;
---
thickness = 3.3mm
Analog |  | To be
---
delivered
Dec 2020
| SLASH
---
(pending)
61 | 400 |  | 2020 model
---
designed for
UH-88
| Convex aspheric
---
slumped glass;
thickness = 3.3mm
Digital | TBD

## References

  * [1] Esposito, S., Riccardi, A., Fini, L., Puglisi, A. T., Pinna, E., Xompero, M., Briguglio, R., Quirós-Pacheco, F., Stefanini, P., Guerra, J. C., Busoni, L., Tozzi, A., Pieralli, F., Agapito, G., Brusa-Zappellini, G., Demers, R., Brynnel, J., Arcidiacono, C., and Salinari, P., “First light AO (FLAO) system for LBT: final integration, acceptance test in Europe, and preliminary on-sky commissioning results,” in [Adaptive Optics Systems II ], Ellerbroek, B. L., Hart, M., Hubin, N., and Wizinowich, P. L., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 7736, 773609 (July 2010).
  * [2] Close, L. M., Males, J. R., Morzinski, K. M., Esposito, S., Riccardi, A., Briguglio, R., Follette, K. B., Wu, Y.-L., Pinna, E., Puglisi, A., Xompero, M., Quiros, F., and Hinz, P. M., “Status of MagAO and review of astronomical science with visible light adaptive optics,” in [Adaptive Optics Systems VI ], Close, L. M., Schreiber, L., and Schmidt, D., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 10703, 107030L (July 2018).
  * [3] Biasi, R., Andrighettoni, M., Angerer, G., Mair, C., Pescoller, D., Lazzarini, P., Anaclerio, E., Mantegazza, M., Gallieni, D., Vernet, E., Arsenault, R., Madec, P. Y., Duhoux, P., Riccardi, A., Xompero, M., Briguglio, R., Manetti, M., and Morandini, M., “VLT deformable secondary mirror: integration and electromechanical tests results,” in [Adaptive Optics Systems III ], Ellerbroek, B. L., Marchetti, E., and Véran, J.-P., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 8447, 84472G (July 2012).
  * [4] Wildi, F. P., Brusa, G., Lloyd-Hart, M., Close, L. M., and Riccardi, A., “First light of the 6.5-m MMT adaptive optics system,” in [Astronomical Adaptive Optics Systems and Applications ], Tyson, R. K. and Lloyd-Hart, M., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 5169, 17–25 (Dec. 2003).
  * [5] Hinz, P. M., Defrère, D., Skemer, A., Bailey, V., Stone, J., Spalding, E., Vaz, A., Pinna, E., Puglisi, A., Esposito, S., Montoya, M., Downey, E., Leisenring, J., Durney, O., Hoffmann, W., Hill, J., Millan-Gabet, R., Mennesson, B., Danchi, W., Morzinski, K., Grenz, P., Skrutskie, M., and Ertel, S., “Overview of LBTI: a multipurpose facility for high spatial resolution observations,” in [Optical and Infrared Interferometry and Imaging V ], Malbet, F., Creech-Eakman, M. J., and Tuthill, P. G., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 9907, 990704 (Aug. 2016).
  * [6] Kuiper, S., Doelman, N., Human, J., Saathof, R., Klop, W., and Maniscalco, M., “Advances of TNO’s electromagnetic deformable mirror development,” in [Advances in Optical and Mechanical Technologies for Telescopes and Instrumentation III ], Navarro, R. and Geyl, R., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 10706, 1070619 (July 2018).
  * [7] Riccardi, A., Brusa, G., Salinari, P., Gallieni, D., Biasi, R., Andrighettoni, M., and Martin, H. M., “Adaptive secondary mirrors for the Large Binocular Telescope,” in [Adaptive Optical System Technologies II ], Wizinowich, P. L. and Bonaccini, D., eds., Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series 4839, 721–732 (Feb. 2003).