No label defined (Q3974856)

[For the entire collection see Zbl 0726.00019.] We show that the jump number of biconvex graphs (a subclass of chordal bipartite graphs) can be determined in polynomial time using several reformulations of the problem and a duality relation between rectangle independent point sets and rectangle covers of rectangular regions known from a result of \textit{S. Chaiken}, \textit{D. J. Kleitman}, \textit{M. Saks} and \textit{J. Shearer} [SIAM J. Alg. Discr. Math., 394-410 (1981; Zbl 0506.05022)] and \textit{D. Franzblau} and \textit{D. J. Kleitman} [An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals, 16th STOC, 167-174 (1984)]. This solves the jump number problem for biconvex graphs by means of computational geometry. Furthermore for bipartite permutation graphs (a subclass of biconvex graphs) the rectangle cover approach yields a greedy solution which is faster than the dynamic programming solution given by \textit{G. Steiner} and \textit{L. Stewart} [A linear time algorithm to find the jump number of 2-dimensional bipartite orders, Order 3, 359-367 (1987; Zbl 0622.06002)]. An optimal rectangle cover can be determined in linear time using the geometric description of the region or the defining permutation.