Efficient deterministic algorithms for embedding graphs on books
- Additional Document Info
- View All
© 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)