Journal
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Volume -, Issue -, Pages -Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0129054123500168
Keywords
Parameterized algorithms; fixed-order; book drawing; pseudo edge; crossings
Categories
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available