A 2-page book embedding of a graph is to place the vertices
linearly on a spine (a line segment) and the edges on the two pages (two
half planes sharing the spine) so that each edge is embedded in one of
the pages without edge crossings. Testing whether a given graph admits a
2-page book embedding is known to be NP-complete. In this paper, we
study the problem of testing whether a given graph admits a 2-page book
embedding with a fixed edge partition. We first show that finding a 2-
page book embedding of a given graph can be reduced to the planarity
testing of a graph, which yields a simple linear-time algorithm for
solving the problem. We also characterize the graphs that do not admit
2-page book embeddings via forbidden subgraphs, and give a linear-time
algorithm for detecting the forbidden subgraph of a given graph.