Planarizing graphs and their drawings by vertex splitting

Abstract

The splitting number of a graph G = (V, E) is the minimum number of vertex splits required to turn G into a planar graph, where a vertex split removes a vertex v ∈ V, introduces two new copies v<inf>1</inf>, v<inf>2</inf> of v, and distributes the edges formerly incident to v among v<inf>1</inf>, v<inf>2</inf>. The splitting number problem, i.e., deciding whether the splitting number is at most k, is known to be NP-complete for non-embedded graphs and we provide a non-uniform fixed-parameter tractable (FPT) algorithm for this problem, parameterized by the number k of vertex splits. We then shift focus to the splitting number of a given topological graph drawing in R², where the new vertices resulting from vertex splits must be re-embedded into the existing drawing of the remaining graph. We show NP-completeness of this embedded splitting number problem, even for its two subproblems where we are given a topological graph drawing with edge crossings and an integer k and we want to (1) select a feasible subset of at most k vertices to split or (2) split a given set of vertices at most k times and re-embed the resulting copies to obtain a plane topological graph. For the latter problem we present an FPT algorithm parameterized by the number k of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition.