Efficient deterministic algorithms for embedding graphs on books
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
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.