Efficient Maximum Matching Algorithms for Trapezoid Graphs

Phan-Thuan Do • Ngoc-Khang Le • Van-Thieu Vu


Trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. Many NP-hard problems can be solved in polynomial time if they are restricted on trapezoid graphs. A matching in a graph is a set of pairwise disjoint edges, and a maximum matching is a matching of maximum size. In this paper, we first propose an $O(n(\log n)^3)$ algorithm for finding a maximum matching in trapezoid graphs, then improve the complexity to $O(n(\log n)^2)$. Finally, we generalize this algorithm to a larger graph class, namely $k$-trapezoid graphs. To the best of our knowledge, these are the first efficient maximum matching algorithms for trapezoid graphs.




Electronic Journal of Graph Theory and Applications

The Electronic Journal of Graph Theory and Applications (EJGTA) is a refereed journal devoted to ... see more