The planar split thickness of a graph is the smallest k such that the graph is k-splittable into a planar graph. A k-split operation replaces each vertex v with at most k new vertices such that for each edge (v,w), there exists at least one edge connecting a pair of new vertices of v and w. We prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph. However, it is possible to approximate the planar split thickness of a graph within a constant factor. Further, We show that for graphs of bounded treewidth, k-splitability is decidable in linear time for a constant k.
(Based on a paper from LATIN 2016 by David Eppstein, Philipp Kindermann, Stephen Kobourov, Giuseppe Liotta, Anna Lubiw, Aude Maignan, Debajyoti Mondal, Hamideh Vosoughpour, Sue Whitesides, and Stephen Wismath.)