Efficient deterministic algorithms for embedding graphs on books Conference Paper uri icon


  • © Springer-Verlag Berlin Heidelberg 1996. We derive deterministic polynomial time algorithms for book embedding of a graph G = (V, E), ¦V¦ = n and ¦E¦ = m. In particular, we present the first deterministic polynomial time algorithm to embed any bipartite graph in O(√m)pages. We then use this algorithm to embed, in polynomial time, any graph G in O(√δ*(G)⋅m)pages, where δ*(G) is the largest minimum degree over all subgraphs of G. Our algorithms are obtained by derandomizing the probabilistic proofs.

author list (cited authors)

  • Shahrokhi, F., & Shi, W.

publication date

  • January 1996