Parameterized Algorithms for Planar 2-Layer Drawing by Vertex Splitting on a Given Subset
摘要
In this work, we study parameterized algorithms for two problems on planar 2-layer graph drawing. At first, we consider the problem bipartite crossing removal with vertex splitting on one side (BCRS), which asks whether a bipartite graph G = \((T\cup B,E)\) admits a planar 2-layer drawing after applying at most k splits to the vertices of B. We show that this problem admits a parameterized algorithm with running time in \(\mathcal O((k+5)^k\cdot m)\) , where m is the number of edges of G. More generally, we consider the problem pathwidth-one vertex splitting (POVS), which asks whether a graph G = (V, E) with a given vertex subset \(S\subseteq V\) can be turned into a graph of pathwidth at most 1 using at most k splits on vertices in S. The POVS problem was shown to admit a parameterized algorithm running in time \(\mathcal O((6k+12)^k\cdot m)\) (WG2023). Here we show that it can be solved in time \(\mathcal O((3k+11)^k\cdot m)\) , where m is the number of edges of G.