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 n vertices and m edges, we present an O(n log n) time algorithm for finding a maximum non-crossing matching in the graph. The previous best algorithm for this problem takes O(m + n log n) time. Since m = Θ(n~2) in the worst case, our result improves the previous solution for large m.