Research On Parameterized Algorithms For Book Drawing Of Graph

Given a graph G=(V,E)and a linear ordering of V along a spine,the Book Drawing problem is to assign the edges of G to the minimum number of pages,which are half-planes bounded by the spine,such that the number of edge-crossings satisfies certain restrictions.This problem,which chiefly consists of Book Embedding and Fixed-order Book Embedding,has a wide range of applications in sorting permutations,bioinformatics,parallel computing and so on.From the perspective of computational complexity,Book Embedding and Fixed-order Book Embedding are all known to be NPcomplete.In this paper,we study the parameterized algorithms for the Book Drawing problem with different structural parameters.Our main results are listed as follows.(1)We investigate parameterized algorithms with respect to the vertex cover number ?.Firstly,we present several new reduction rules in the kernelization procedure for the Book Embedding problem,and propose a parameterized algorithm running in time O(22O(?)+?·|V|),improving the previous one of time O(2?O(?)+?·|V|).For the Fixed-order Book Embedding problem,we re-analyze the algorithm presented by Bhore et al..By introducing a new technique named edge-shifting,we obtain a running time bound of 2O(?2log?)·|V|)improving Bhore et al.'s bound of 2O(?3)·|V|).Then,we show that the Fixed-order Book Drawing problem,in which at most b crossings over all pages are allowed,admits a parameterized algorithm of running time 2O((?2+b?)log?(b+1))·|V|)by employing the edgeshifting technique.(2)We investigate parameterized algorithms with respect to the pathwidth ? of the vertex ordering.First of all,we re-analyze the algorithm presented by Bhore et al.for the Fixed-order Book Embedding problem.By introducing the edge-pruning technique,we obtain a running time bound of 2O(?2)improving Bhore et al.'s bound of ?O(?2)·|V|.Next,we prove that Fixed-order Book Embedding parameterized by the pathwidth of vertex ordering has no polynomial kernel unless NP?coNP/poly by employing the And-cross-composition framework.Furthermore,we show that the Fixed-order Book Drawing problem admits a parameterized algorithm of running time(b+2)O(?2)·|V| by using edge-shifting,in which b denotes the maximum number of edge-crossings over all pages.(3)We propose parameterized algorithms with respect to multiple structural parameters.For the generalized Fixed-order Book Drawing problem,in which the maximum number of crossings per edge is at most ?,we present two parameterized algorithms respectively.First,we develop a parameterized algorithm of running time(?+2)O(?3)·|V|with respect to both the maximum number ? of crossings per edge and the vertex cover number ?.Then,we present a parameterized algorithm of running time(?+2)O(?2)·|V|with respect to both the maximum number ? of crossings per edge and the pathwidth ? of the vertex ordering.Ours results form a special answer to a question posed by Bhore et al.