Optimal Partition of a Bipartite Graph with Prescribed Layout into NonCrossing Matchings

Given a bipartite graph and a prescribed layout of it, we
address the problem of partitioning the edge set of the graph into the
minimum number of noncrossing matchings, that is subsets of edges
no two of which share a common vertex or cross each other in the
plane. We discuss some lower and upper bounds on the minimum
number of classes of such a partition into noncrossing matchings, and
devise an exact almost linear algorithm.