Abstract

We model maximum cross-free matchings and minimum biclique covers of two-directional orthogonal ray graphs (2-dorgs) as maximum independent sets and minimum hitting sets of an associated family of rectangles in the plane, respectively. We then compute the corresponding maximum independent set using linear programming and uncrossing techniques. This procedure motivates an efficient combinatorial algorithm to find a cross-free matching and a biclique cover of the same cardinality, proving the corresponding min-max relation. We connect this min-max relation with thework ofGyori [19], Lubiw[23], and Frank and Jordan [16] on seemingly unrelated problems. Our result can be seen as a non-trivial application of Frank and Jord ' an's Theorem. As a direct consequence, we obtain the first polynomial algorithm for the jump number problem on 2-dorgs. For the subclass of convex graphs, our approach is a vast improvement over previous algorithms. Additionally, we prove that the weighted maximum cross-free matching problem is NP-complete for 2-dorgs and give polynomial algorithms for some subclasses.