Jump number of two-directional orthogonal ray graphs

José A. Soto, Claudio Telha

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

19 Scopus citations


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 the work of Györi, [19] Lubiw [23], and Frank and Jordán [16] on seemingly unrelated problems. Our result can be seen as a non-trivial application of Frank and Jordán'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.

Original languageEnglish
Title of host publicationInteger Programming and Combinatoral Optimization - 15th International Conference, IPCO 2011, Proceedings
Number of pages15
StatePublished - 2011
Event15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011 - New York, NY, United States
Duration: 15 Jun 201117 Jun 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6655 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011
Country/TerritoryUnited States
CityNew York, NY


Dive into the research topics of 'Jump number of two-directional orthogonal ray graphs'. Together they form a unique fingerprint.

Cite this