I'm trying to identify an algorithm to solve this computational problem
- Bipartite graph
(V, W, E), with
E ⊆ V×W
- A fixed order for both
V = (v1, ..., vn)and
W = (w1, ..., wm)
- The subset of
Eof 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
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?