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.