scientific article; zbMATH DE number 17532

DOI10.1007/3-540-51498-8_7MaRDI QIDQ3974856zbMATH OpenFDO

Authors Andreas Brandstädt

Publication date 26 June 1992

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-51498-8_7

zbMATH Keywords

biconvex graphsbipartite permutation graphsrectangle coversrectangle independent point sets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

[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.

Recommendations

• Jump number of two-directional orthogonal ray graphs
• scientific article; zbMATH DE number 29609
• On the jump number problem in hereditary classes of bipartite graphs
• An algorithm for covering polygons with rectangles
• Biconvex graphs: Ordering and algorithms

Cited in

(7)

• Alternating cycle-free matchings
• Biconvex graphs: Ordering and algorithms
• Independent sets and hitting sets of bicolored rectangular families
• Bypasses for rectangular diagrams. A proof of the Jones conjecture and related questions
• Jump number of two-directional orthogonal ray graphs
• The computation of the jump number of convex graphs
• Contiguity orders

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3974856)