Article ID: | iaor1995282 |
Country: | Netherlands |
Volume: | 47 |
Issue: | 2 |
Start Page Number: | 175 |
End Page Number: | 179 |
Publication Date: | Nov 1993 |
Journal: | Discrete Applied Mathematics |
Authors: | Malucelli Federico, Ottman Thomas, Pretolani Daniele |
Keywords: | combinatorial analysis |
Consider a bipartite graph; let’s suppose the origin nodes and the destination nodes are drawn, arranged in two columns, and the edges as straight-line segments. A noncrossing matching is a subset of edges such that no two of them intersect. Several algorithms for the problem of finding the noncrossing matching of maximum cardinality are proposed. Moreover an extension to weighted graphs is considered.