Optimal Partition of a Bipartite Graph with prescribed layout into Non-Crossing 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 non-crossing 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 non-crossing matchings, and devise an exact almost linear algorithm.