Two-Page Book Embedding


S. Hong and H. Nagamochi, "Simpler Algorithms for Testing Two-Page Book Embedding of Partitioned Graphs", Proceedings of COCOON 2014, pp. 477-488, LNCS, Springer, 2014.

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 then 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.



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