摘要: Let G=(V,E) be a t-partite graph with n vertices and m edges, where the partite sets are given. We present an O(n2m1.5) time algorithm to construct drawings of G in plane so that size largest set pairwise crossing edges and, at same time, disjoint (pairwise noncrossing) Ot·m. As application we embed book Ot·m pages, resolving open question for pagenumber problem. A similar result is obtained dual or queuenumber. Our algorithms by derandomizing probabilistic proof.
elsevier.com
sci-hub.se 参考文章(25)
P. Valtr, On geometric graphs with no k pairwise parallel edges Discrete and Computational Geometry. ,vol. 19, pp. 461- 469 ,(1997) , 10.1007/PL00009364
Fan R. K. Chung, Frank Thomson Leighton, Arnold L. Rosenberg, Embedding graphs in books: a layout problem with applications to VLSI design Siam Journal on Algebraic and Discrete Methods. ,vol. 8, pp. 33- 58 ,(1987) , 10.1137/0608002
Lenwood S. Heath, Sorin Istrail, The pagenumber of genus
g
graphs is O(
g
) Journal of the ACM. ,vol. 39, pp. 479- 501 ,(1992) , 10.1145/146637.146643
Lenwood S. Heath, Frank Thomson Leighton, Arnold L. Rosenberg, Comparing queues and stacks as mechanisms for laying out graphs SIAM Journal on Discrete Mathematics. ,vol. 5, pp. 398- 412 ,(1992) , 10.1137/0405031
S.M. Malitz, Genus g graphs have pagenumber O g Journal of Algorithms. ,vol. 17, pp. 85- 109 ,(1994) , 10.1006/JAGM.1994.1028
S.M. Malitz, Graphs with E edges have pagenumber E O Journal of Algorithms. ,vol. 17, pp. 71- 84 ,(1994) , 10.1006/JAGM.1994.1027
Lenwood S. Heath, Arnold L. Rosenberg, Laying out graphs using queues SIAM Journal on Computing. ,vol. 21, pp. 927- 958 ,(1992) , 10.1137/0221055
Frank Bernhart, Paul C Kainen, The book thickness of a graph Journal of Combinatorial Theory, Series B. ,vol. 27, pp. 320- 331 ,(1979) , 10.1016/0095-8956(79)90021-2
L.G. Valiant, The complexity of computing the permanent Theoretical Computer Science. ,vol. 8, pp. 189- 201 ,(1979) , 10.1016/0304-3975(79)90044-6
J. Pach, F. Shahrokhi, M. Szegedy, Applications of the crossing number Algorithmica. ,vol. 16, pp. 111- 117 ,(1996) , 10.1007/BF02086610