Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation

Question

I'm trying to identify an algorithm to solve this computational problem

Input:

• Bipartite graph (V, W, E), with E ⊆ V×W
• A fixed order for both V and W: V = (v1, ..., vn) and W = (w1, ..., wm)

Output:

• The subset of E of maximum cardinality in which there are no crossing edges.

The mental image is that the two vertex sets are arranged in two parallel arrays with edges between them, which may or may not cross. More formally, edges (vk, wl) and (vp, wq) cross if either 1) k < l and p > q, or 2) k > l and p < q.

Does anyone know about any published literature on this problem?

It seems that there is a much larger body of literature on the problem of choosing permutations of V and W to minimize edge crossing, which is NP-Hard. However, I'm working with a fixed permutation for both sets.

I've also identified a few papers that count the number of edge crossings under a fixed permutation:

• Waddle & Malhotra (2000) An E log E Line Crossing Algorithm for Levelled Graphs
• Barth, et al (2002) Simple and Efficient Bilayer Cross Counting
• Nagamochi & Yamada (2004) Counting edge crossings in a 2-layered drawing

However, none of these papers discuss the problem of minimizing edge crossings by removing edges.

There are a few more papers in which the algorithm selects a maximum non-crossing matching under a fixed permutation.

• Widmayer & Wong (1985) An optimal algorithm for the maximum alignment of terminals
• Malucelli, et al. (1993) Efficient labelling algorithms for the maximum noncrossing matching problem

This is closer to the mark since it's maximizing the cardinality of an edge set, but I don't want to restrict the edge set to being a matching. Any leads?

Answer 1

Without loss of generality, assume every vertex has degree 1. Create $\deg(u)$ copies of a vertex $u$, then sort the created vertices in the order of the opposite vertex of the corresponding edge.

Then, the bipartite graph can be represented by a permutation as in permutation graphs. Now, a set of edges in the bipartite graph is non-crossing if and only if the corresponding sub-sequence of the permutation is increasing. This longest increasing subsequence problem is solvable in $O(n \log n)$ time, therefore the original problem is solvable in $O((|V| + |W| + |E|) \log (|V| + |W| + |E|))$ time.