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 pla-narity 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 em-beddings via forbidden subgraphs, and give a linear-time algorithm for detecting the forbidden subgraph of a given graph.
展开▼
