Computing maximum non-crossing matching in convex bipartite graphs

We consider computing a maximum non-crossing matching in convex bipartite graphs. For a convex bipartite graph of nn vertices and mm edges, we present an O(nlogn)O(nlogn) time algorithm for finding a maximum non-crossing matching in the graph. The previous best algorithm takes O(m+nlogn)O(m+nlogn) time (Malucelli et al., 1993). Since m=Θ(n2)m=Θ(n2) in the worst case, our result improves the previous work.