Book Embedding with Fixed Page Assignments
Daniel Hoske · 2012
A k-page book embedding of a graph is a drawing of that graph in a book, with vertices along the book’s spine (a straight line) and edges in k of the book’s pages (half planes with the spine as boundary) such that the edges do not cross. In this thesis we consider the problem of determining whether such a drawing exists when the assignment of edges to pages is predetermined. We start by showing that this problem is NP-complete for an unbounded number of pages, even if the edges on each page form a matching, and then solve some special cases thereof. In the case of connected graphs on each page, we provide a linear-time decision algorithm. When the graphs on each page are disjoint perfect matchings, we show that the graph has to be bipartite to be embeddable and give bipartite examples and counterexamples. Following these results, we consider several variations of the problem. Firstly, if we constrain the vertex orders on the spine by a PQ-tree only containing Q-nodes as inner nodes, embeddability can be decided in quadratic time. Secondly, we alter the embedding problem by taking multiple spines (parallel lines) in the plane and associating every vertex with a spine the vertex has to be drawn on. Additionally, edges must be drawn between consecutive spines, above the topmost spine or below the bottommost spine. We show that this variation is equivalent to a special case of the 2-page book embedding problem with fixed page assignments where the vertex order is constrained by a PQtree only containing P-nodes as inner nodes. At the end we outline the most important open problems for book embedding with fixed page assignments and provide some suggestions on how to approach them.