A linear time algorithm for maximum matchings in convex, bipartite graphs

The problem of determining the maximum matching in a convex bipartite graph, G=(V1,V2,E), is considered. It is shown that by using the appropriate data structures, the maximum matching problem can be efficiently transformed into an off-line minimum problem. Since the off-line minimum problem has been shown to be linear, the maximum matching in a convex bipartite graph can be determined in O(ℝV1ℝ) time.