S. Hong and H. Nagamochi, "Two-page Book Embedding and Clustered Graph Planarity" , TR [2009-004], Department of Applied Mathematics and Physics, Graduate School of Informatics, University of Kyoto, Japan, 2009.
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