×

On crossing sets, disjoint sets, and pagenumber. (English) Zbl 0958.68130

Summary: Let \(G= (V, E)\) be a \(t\)-partite graph with \(n\) vertices and \(m\) edges, where the partite sets are given. The authors present an \(O(n^2 m^{1.5})\) time algorithm to construct drawings of \(G\) in the plane so that the size of the largest set of pairwise crossing edges and, at the same time, the size of the largest set of disjoint (pairwise noncrossing) edges are \(O(\sqrt{t\cdot m})\). As an application they embed \(G\) in a book of \(O(\sqrt{t\cdot m})\) pages, in \(O(n^2 m^{1.5})\) time, resolving an open question for the pagenumber problem. A similar result is obtained for the dual of the pagenumber or the queuenumber. Their algorithms are obtained by derandomizing a probabilistic proof.

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI