Vertex-Bipartition: A Unified Approach for Kernelization of Graph Linear Layout Problems Parameterized by Vertex Cover.

The Linear Layout of Graphs problem asks, given a graph G and a positive integer k , whether G admits a layout consisting of a linear ordering of its vertices and a partition of its edges into k sets such that the edges in each set meet some special requirements. Specific linear layouts include k -Stack Layout, k -Queue Layout, k -Arch Layout, Mixed s -Stack q -Queue Layout and others. In this paper, we present a unified approach for kernelization of these linear layout problems parameterized by the vertex cover number τ of the input graph. The key point underlying our approach is to partition each set of related vertices into two distinct subsets with respect to the specific layouts, which immediately leads to some efficient reduction rules. We first apply this approach to the Mixed s -Stack q -Queue Layout problem and show that it admits a kernel of size 2 (τ) , which results in an algorithm running in time (2 2 (τ) + τ ⋅ | V |) , where | V | denotes the size of the input graph. Our work does not only confirm the existence of a fixed-parameter tractable algorithm for this problem mentioned by Bhore et al. (J. Graph Algorithms Appl. 2022), but also derives new results for the k -Stack Layout problem and for the k -Queue Layout problem respectively. We also employ this approach to the Upward k -Stack Layout problem and obtain a new result improving that presented by Bhore et al. (GD 2021). Last but not least, we use this approach to the k -Arch Layout problem and obtain a similar result. [ABSTRACT FROM AUTHOR]