# Planarizing Graphs and their Drawings by Vertex Splitting

arXiv: https://arxiv.org/abs/2202.12293 · HTML: https://mlsanity.com/paper/2202.12293/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2022.

## Built on by (most cited first, 1 of 1)

- [When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting](https://mlsanity.com/paper/2605.23540/) (2026)

## Abstract (arXiv)

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 vertices v1, v2, and distributes the edges formerly incident to v among its two split copies v1, v2. The splitting number problem is known to be NP-complete. In this paper we shift focus to the splitting number of graph drawings in mathbb R2, where the new vertices resulting from vertex splits can be re-embedded into the existing drawing of the remaining graph. We first provide a non-uniform fixed-parameter tractable (FPT) algorithm for the splitting number problem (without drawings). Then we show the NP-completeness of the splitting number problem for graph drawings, even for its two subproblems of (1) selecting a minimum subset of vertices to split and (2) for re-embedding a minimum number of copies of a given set of vertices. For the latter problem we present an FPT algorithm parameterized by the number of vertex splits. This algorithm reduces to a bounded outerplanarity case and uses an intricate dynamic program on a sphere-cut decomposition.