ICS Theory Group

Winter 2017: Theory Seminar
Bren Hall, Room 1300, 1:00pm

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.)