期刊
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
卷 -, 期 -, 页码 -出版社
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0129054123500168
关键词
Parameterized algorithms; fixed-order; book drawing; pseudo edge; crossings
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据