Just Accepted
This paper has been accepted to be published in the JGAA Special issue on Selected papers from the Twenty-seventh 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.
Parameterized Algorithms for Book Embedding Problems
Vol. 0, no. 0, pp. 0-0, 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$ 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 ${\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 fixed-parameter 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 fixed-parameter 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 on-line: April 2020.
Communicated by Daniel Archambault and Csaba D. Tóth
article (PDF)