A Faster Parameterized Algorithm for Bipartite 1-Sided Vertex Explosion

Given a bipartite graph G = \((T\cup B,E)\) , the problem bipartite 1-sided vertex explosion is to decide whether there exists a planar 2-layer embedding of G after exploding at most k vertices of B. For this problem, which is known to be NP-complete, parameterized algorithms have received increasing attention more recently. In this paper, we focus on the problem parameterized by the number k of allowed exploded vertices of B and develop a faster algorithm for it. More specifically, we show that this parameterized problem admits a kernel of at most 10.5k vertices, and present a fixed-parameter tractable algorithm running in time \(\mathcal O(2.31^k\cdot m)\) , where m is the number of edges of G.