A 2-page book embedding of a graph places
the vertices linearly on a spine (a line segment)
and the edges on 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.
Based on structural properties of planar graphs,
we prove that the problem of testing and finding
a 2-page book embedding of a graph with a partitioned
edge set can be solved in linear time.
As an application of our main result, we consider
the problem of testing planarity of clustered graphs.
The complexity of testing clustered graph planarity
is a long standing open problem in Graph
Drawing. Recently, polynomial time algorithms
have been found for
several classes of clustered graphs in which both
the structure of the underlying graphs and
clustering structure are restricted.
However, when the underlying graph is disconnected,
the problem remains open. Our book embedding results
imply that the clustered
planarity problem can be solved in linear time for a certain class
of clustered graphs with arbitrary underlying graphs
(i.e. possibly disconnected).