Parameterized Algorithms for Book Embedding Problems
A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called FIXED-ORDER BOOK THICKNESS , or not fixed, called BOOK THICKNESS . Both problems are known to be NP-complete in general. We show that FIXED-ORDER BOOK THICKNESS and BOOK THICKNESS are fixed-parameter tractable parameterized by the vertex cover number of the graph and that FIXED-ORDER BOOK THICKNESS is fixed-parameter tractable parameterized by the pathwidth of the vertex order. , number=4, journal=Journal of Graph Algorithms and Applications, author=Bhore, Sujoy and Ganian, Robert and Montecchiani, Fabrizio and Nöllenburg, Martin, year=2020, month=Dec., pages=603–620