Home  Issues  Aims and Scope  Instructions for Authors 
Just Accepted
This paper has been accepted to be published in the JGAA Special issue on Selected papers from the Twentyseventh International Symposium on Graph Drawing and Network Visualization, GD 2019. The paper will receive a volume, an issue number, and page numbers when the whole special issue will be published.
DOI: 10.7155/jgaa.00526
Parameterized Algorithms for Book Embedding Problems
Vol. 0, no. 0, pp. 00, 0. Regular paper.
Abstract A $k$page book embedding of a graph $G$ draws the vertices of $G$ on a line and the edges on $k$ halfplanes (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 ${\rm F{\small IXED}O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$, or not fixed, called ${\rm B{\small OOK}~T{\small HICKNESS}}$. Both problems are known to be ${\sf NP}$complete in general. We show that ${\rm F{\small IXED}O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$ and ${\rm B{\small OOK}~T{\small HICKNESS}}$ are fixedparameter tractable parameterized by the vertex cover number of the graph and that ${\rm F{\small IXED}O{\small RDER}~B{\small OOK}~T{\small HICKNESS}}$ is fixedparameter tractable parameterized by the pathwidth of the vertex order.

Submitted: October 2019.
Reviewed: January 2020.
Revised: March 2020.
Accepted: April 2020.
Final: April 2020.
Appeared online: April 2020.
