## March 3, 2017:

#
On the Planar Split Thickness of Graphs

##
Elham Havvaei

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 $\mathsf{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.)