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.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Shahrokhi, F., & Shi, W.

complete list of authors

  • Shahrokhi, F||Shi, W

publication date

  • January 1996