No label defined (Q4948670)

A geometric bipartite graph \(G=(V,E)\) is defined in the article as a graph whose vertices are points on the plain such that \(V = X \cup Y\), where sets \(X\) and \(Y\) lie on two parallel lines, and edges are segments \(E \subseteq \{[x,y]\mid x \in X\) and \(y \in Y \}\). A subset \(M\) of \(E\) is a geometric matching in G if the segments in \(M\) are pairwise disjoint. A graph \(G=(X \cup Y,E)\) is said to have a canonical form if \(|X|=|Y|=|E|\) and all vertices are of degree one. Thus, a canonical geometric bipartite graph is equivalent to a permutation graph, and matching problems on canonical geometric bipartite graphs correspond to problems on permutation graphs. The author considers four natural problems on geometric matchings (in particular, the maximum geometric matching problem) in geometric bipartite weighted graphs. Effective algorithms for solving these problems are given and discussed.