  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 \NP-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.
