Parameterized Algorithms for Fixed-Order Book Drawing with Few Crossings Per Edge

Given ann-vertex graphGwith a fixed linear ordering ofV(G) and two integersk,b,the problemfixed-order book drawingwith few crossings per edge asks whether ornotGadmits ak-page book drawing where the maximum number of crossings per edgecan be upper bounded by the numberb. This problem was posed as an open question byBhoreet al.(J. Graph Algorithms Appl.2020). In this paper, we study this problem fromthe viewpoint of parameterized complexity, in particular, we develop fixed-parametertractable algorithms for it. More specifically, we show that this problem parameterizedby both the bound numberbof crossings per edge and the vertex cover number tau of the input graph admits an algorithm with running time in (b+ 2)O(tau(3))n, and this problem parameterized by both the bound numberbof crossings per edge and the pathwidth kappa of the vertex ordering admits an algorithm with running time in (b+ 2)O(kappa(2))n. Ourresults provide a specific answer to Bhoreet al.'s question.

Automated summary

In this paper, we study the fixed-order book drawing problem and develop algorithms for it from the perspective of parameterized complexity. By limiting the number of crossings per edge and other parameters of the input graph, we obtain specific results.